Submission #204087


Source Code Expand

Copy
#include <iostream>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <complex>

using namespace std;

typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<long, long> pl;
typedef pair<double, double> pd;
typedef vector<pi> vpi;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<long, long> vll;
typedef vector<double> vec;
typedef vector<vec> mat;
typedef map<int, int> mii;
void dumppi(const pi &p) {  cout << p.first  << ' ' << p.second << endl; }
typedef pair<long, long> pl;
void dumppl(const pl &p) { cout << p.first << ' ' << p.second << endl; }
typedef vector<pi> vpi;
void dumpvpi(const vpi &vec) { for (auto v : vec) { cout << '(' << v.first << ',' << v.second << ')' << ' '; } cout << endl; }
typedef vector<bool> vb;
void dumpvb(const vb &vec) { for (auto b : vec) { cout << b << ' '; } cout << endl; }
typedef vector<int> vi;
void dumpvi(const vi &vec) { for (auto i : vec) { cout << i << ' '; } cout << endl; }
typedef vector<pl> vpl;
void dumpvpi(const vpl &vec) { for (auto v : vec) { cout << '(' << v.first << ',' << v.second << ')' << ' '; } cout << endl; }
typedef vector<vi> vii;
void dumpvii(const vii &mat) {for (auto vec : mat) {for (auto v : vec){cout << v << ' ';} cout << endl;}}


// util macro
// ----------------------------------------
#define mp make_pair
#define pb push_back
//-----------------------------------------

// iterator
// ----------------------------------------
#define all(x) (x).begin(), (x).end()
// ----------------------------------------

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
//------------------------------------------

const int INF = 1e9;
const double EPS = 1e-10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = { 0,-1, 0, 1};

const int mod = 100007;
const double g = 9.8;

// POINTS
//-------------------------------------------
typedef complex<double> point;
// X : real();
// Y : imag();
double dot(point a, point b){  // inner product
    return (a * conj(b)).real();
}
double cross(point a, point b){ // outer product
    return (a * conj(b)).imag();
}
double dist(point a, point b) {
    return dot(a-b, a-b);
}
typedef vector<point> vpoint;
//-------------------------------------------

#define  debu 0

ll W, H, N;
vpi machines;

map<string, ll> dp;
ll dfs(ll x1, ll y1, ll x2, ll y2) {
    // if overed map, return 0;
    stringstream ss;
    ss << x1 << " " << y1 << " " << x2 << " " << y2;
    string key = ss.str();
    // cout << "start=" << key << endl;
    if (dp.find(key) != dp.end()) {
        return dp[key];
    }
    
    
    
    ll maxans = 0;
    for (auto point : machines) {
        if (point.first >= x1 && point.first <= x2 && point.second >= y1 && point.second <= y2) {
            ll ans = 0;
            
            ans += dfs(x1, y1, point.first-1, point.second-1); // left bottom
            ans += dfs(x1, point.second+1, point.first-1, y2); // left upper
            ans += dfs(point.first+1, y1, x2, point.second-1); // right bottom
            ans += dfs(point.first+1, point.second+1, x2, y2); // right upper
            
            ll gold = (x2 - x1 + 1) + (y2 - y1 + 1) - 1;
            ans += gold;
            maxans = max(maxans, ans);
        }
    }
#if debu
    cout << key << " ans=" << maxans << endl;
#endif
    return dp[key] = maxans;;
}


int main(int argc, const char * argv[])
{
    ios::sync_with_stdio(false);
    cin >> W >> H >> N;

    rep(i, N) {
        ll x, y;
        cin >> x >> y;
        machines.push_back(mp(x, y));
    }
    
    cout << dfs(1, 1, W, H) << endl;
    
    return 0;
}

Submission Info

Submission Time
Task D - 金塊ゲーム
User nida_001
Language C++11 (GCC 4.8.1)
Score 100
Code Size 4003 Byte
Status
Exec Time 245 ms
Memory 2340 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 80 / 80 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt
Subtask2 19 / 19 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt
Subtask3 1 / 1 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask3_13.txt, subtask3_14.txt, subtask3_15.txt, subtask3_16.txt, subtask3_17.txt, subtask3_18.txt, subtask3_19.txt, subtask3_20.txt, subtask3_21.txt, subtask3_22.txt, subtask3_23.txt, subtask3_24.txt, subtask3_25.txt
Case Name Status Exec Time Memory
sample_01.txt 22 ms 736 KB
sample_02.txt 21 ms 928 KB
sample_03.txt 22 ms 932 KB
subtask1_01.txt 21 ms 812 KB
subtask1_02.txt 20 ms 800 KB
subtask1_03.txt 22 ms 928 KB
subtask1_04.txt 30 ms 804 KB
subtask1_05.txt 24 ms 928 KB
subtask1_06.txt 22 ms 932 KB
subtask1_07.txt 20 ms 928 KB
subtask1_08.txt 20 ms 924 KB
subtask1_09.txt 21 ms 800 KB
subtask1_10.txt 21 ms 796 KB
subtask1_11.txt 21 ms 796 KB
subtask1_12.txt 20 ms 800 KB
subtask1_13.txt 20 ms 824 KB
subtask1_14.txt 21 ms 932 KB
subtask1_15.txt 22 ms 928 KB
subtask1_16.txt 23 ms 800 KB
subtask1_17.txt 21 ms 924 KB
subtask1_18.txt 24 ms 812 KB
subtask1_19.txt 24 ms 804 KB
subtask1_20.txt 23 ms 796 KB
subtask1_21.txt 24 ms 928 KB
subtask1_22.txt 22 ms 928 KB
subtask1_23.txt 27 ms 928 KB
subtask1_24.txt 23 ms 932 KB
subtask1_25.txt 24 ms 924 KB
subtask2_01.txt 34 ms 928 KB
subtask2_02.txt 35 ms 924 KB
subtask2_03.txt 59 ms 1192 KB
subtask2_04.txt 67 ms 1188 KB
subtask2_05.txt 115 ms 1364 KB
subtask2_06.txt 117 ms 1436 KB
subtask2_07.txt 114 ms 1436 KB
subtask2_08.txt 112 ms 1440 KB
subtask2_09.txt 245 ms 1956 KB
subtask2_10.txt 212 ms 1956 KB
subtask2_11.txt 201 ms 1964 KB
subtask2_12.txt 215 ms 1908 KB
subtask2_13.txt 116 ms 1444 KB
subtask2_14.txt 116 ms 1448 KB
subtask2_15.txt 27 ms 916 KB
subtask2_16.txt 115 ms 1452 KB
subtask2_17.txt 206 ms 1948 KB
subtask2_18.txt 216 ms 1956 KB
subtask2_19.txt 203 ms 1956 KB
subtask2_20.txt 204 ms 1952 KB
subtask2_21.txt 211 ms 1956 KB
subtask2_22.txt 205 ms 1960 KB
subtask2_23.txt 225 ms 1956 KB
subtask2_24.txt 210 ms 1956 KB
subtask2_25.txt 224 ms 1952 KB
subtask3_01.txt 22 ms 928 KB
subtask3_02.txt 36 ms 928 KB
subtask3_03.txt 35 ms 928 KB
subtask3_04.txt 47 ms 1052 KB
subtask3_05.txt 80 ms 1268 KB
subtask3_06.txt 64 ms 1180 KB
subtask3_07.txt 61 ms 1176 KB
subtask3_08.txt 117 ms 1576 KB
subtask3_09.txt 133 ms 1584 KB
subtask3_10.txt 229 ms 2088 KB
subtask3_11.txt 209 ms 2144 KB
subtask3_12.txt 232 ms 2076 KB
subtask3_13.txt 236 ms 2204 KB
subtask3_14.txt 232 ms 2080 KB
subtask3_15.txt 221 ms 2076 KB
subtask3_16.txt 217 ms 2284 KB
subtask3_17.txt 234 ms 2140 KB
subtask3_18.txt 91 ms 1448 KB
subtask3_19.txt 211 ms 2212 KB
subtask3_20.txt 114 ms 1560 KB
subtask3_21.txt 233 ms 2220 KB
subtask3_22.txt 242 ms 2208 KB
subtask3_23.txt 227 ms 2340 KB
subtask3_24.txt 222 ms 2216 KB
subtask3_25.txt 218 ms 2216 KB