Contest Duration: - (local time) (120 minutes) Back to Home

Submission #169520

Source Code Expand

Copy
```#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)

int W, H, N;
vector<pii> p;
vector<int> X;
vector<int> Y;

map<int, int> toX;
map<int, int> toY;

ll memo[35][35][35][35];

ll dp(int sx, int dx, int sy, int dy){
ll &Memo = memo[sx][dx][sy][dy];
if(Memo >= 0) return Memo;
if(sx == dx || sy == dy) return Memo = 0;
ll res = 0;
int f = 0;
FOR(it, p){
int x = toX[it->first];
int y = toY[it->second];
if(x<=sx || dx<=x || y<=sy || dy<=y) continue;
//		else printf("%d %d\n", x, y);
res = max(res, dp(sx, x, sy ,y)+dp(sx, x, y ,dy)+dp(x, dx, sy ,y)+dp(x, dx, y ,dy));
f = 1;
}
if(f) res += X[dx]-X[sx] + Y[dy]-Y[sy] - 3;
//	printf("%d %d %d %d = %lld\n", X[sx], Y[sy], X[dx], Y[dy], res);
return Memo = res;
}

main(){
memset(memo, -1, sizeof(memo));
cin >> W >> H >> N;
X.push_back(0);
X.push_back(W+1);
Y.push_back(0);
Y.push_back(H+1);
REP(i, N){
ll x, y;
cin >> x >> y;
p.push_back(pii(x, y));
X.push_back(x);
Y.push_back(y);
}
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
REP(i, X.size()) toX[X[i]] = i;
REP(i, Y.size()) toY[Y[i]] = i;
sort(p.begin(), p.end());
cout << dp(0, (int)X.size()-1, 0, (int)Y.size()-1) << endl;
return 0;
}
```

#### Submission Info

Submission Time 2014-05-10 22:06:45+0900 D - 金塊ゲーム zerokugi C++ (G++ 4.6.4) 100 1703 Byte AC 69 ms 12592 KB

#### Judge Result

Score / Max Score 0 / 0 80 / 80 19 / 19 1 / 1
Status
 AC × 3
 AC × 25
 AC × 50
 AC × 75
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt AC 41 ms 12516 KB
sample_02.txt AC 43 ms 12508 KB
sample_03.txt AC 39 ms 12528 KB
subtask1_01.txt AC 42 ms 12520 KB
subtask1_02.txt AC 43 ms 12528 KB
subtask1_03.txt AC 42 ms 12528 KB
subtask1_04.txt AC 42 ms 12516 KB
subtask1_05.txt AC 43 ms 12516 KB
subtask1_06.txt AC 43 ms 12508 KB
subtask1_07.txt AC 40 ms 12528 KB
subtask1_08.txt AC 42 ms 12520 KB
subtask1_09.txt AC 39 ms 12520 KB
subtask1_10.txt AC 39 ms 12520 KB
subtask1_11.txt AC 43 ms 12524 KB
subtask1_12.txt AC 43 ms 12508 KB
subtask1_13.txt AC 41 ms 12532 KB
subtask1_14.txt AC 43 ms 12516 KB
subtask1_15.txt AC 40 ms 12524 KB
subtask1_16.txt AC 43 ms 12512 KB
subtask1_17.txt AC 43 ms 12520 KB
subtask1_18.txt AC 40 ms 12524 KB
subtask1_19.txt AC 43 ms 12524 KB
subtask1_20.txt AC 40 ms 12524 KB
subtask1_21.txt AC 43 ms 12524 KB
subtask1_22.txt AC 39 ms 12584 KB
subtask1_23.txt AC 39 ms 12524 KB
subtask1_24.txt AC 40 ms 12588 KB
subtask1_25.txt AC 40 ms 12580 KB
subtask2_01.txt AC 45 ms 12524 KB
subtask2_02.txt AC 41 ms 12520 KB
subtask2_03.txt AC 43 ms 12516 KB
subtask2_04.txt AC 43 ms 12520 KB
subtask2_05.txt AC 49 ms 12520 KB
subtask2_06.txt AC 53 ms 12516 KB
subtask2_07.txt AC 51 ms 12516 KB
subtask2_08.txt AC 50 ms 12580 KB
subtask2_09.txt AC 63 ms 12516 KB
subtask2_10.txt AC 62 ms 12524 KB
subtask2_11.txt AC 64 ms 12520 KB
subtask2_12.txt AC 63 ms 12524 KB
subtask2_13.txt AC 50 ms 12524 KB
subtask2_14.txt AC 50 ms 12524 KB
subtask2_15.txt AC 43 ms 12528 KB
subtask2_16.txt AC 50 ms 12520 KB
subtask2_17.txt AC 67 ms 12524 KB
subtask2_18.txt AC 66 ms 12520 KB
subtask2_19.txt AC 65 ms 12528 KB
subtask2_20.txt AC 66 ms 12520 KB
subtask2_21.txt AC 66 ms 12520 KB
subtask2_22.txt AC 66 ms 12528 KB
subtask2_23.txt AC 68 ms 12588 KB
subtask2_24.txt AC 67 ms 12524 KB
subtask2_25.txt AC 67 ms 12520 KB
subtask3_01.txt AC 43 ms 12528 KB
subtask3_02.txt AC 44 ms 12528 KB
subtask3_03.txt AC 40 ms 12520 KB
subtask3_04.txt AC 43 ms 12516 KB
subtask3_05.txt AC 51 ms 12520 KB
subtask3_06.txt AC 48 ms 12520 KB
subtask3_07.txt AC 48 ms 12512 KB
subtask3_08.txt AC 56 ms 12520 KB
subtask3_09.txt AC 51 ms 12528 KB
subtask3_10.txt AC 66 ms 12592 KB
subtask3_11.txt AC 62 ms 12516 KB
subtask3_12.txt AC 67 ms 12520 KB
subtask3_13.txt AC 66 ms 12516 KB
subtask3_14.txt AC 65 ms 12524 KB
subtask3_15.txt AC 67 ms 12524 KB
subtask3_16.txt AC 69 ms 12520 KB
subtask3_17.txt AC 67 ms 12528 KB
subtask3_18.txt AC 48 ms 12524 KB
subtask3_19.txt AC 64 ms 12520 KB
subtask3_20.txt AC 50 ms 12524 KB
subtask3_21.txt AC 65 ms 12524 KB
subtask3_22.txt AC 68 ms 12524 KB
subtask3_23.txt AC 68 ms 12524 KB
subtask3_24.txt AC 69 ms 12528 KB
subtask3_25.txt AC 67 ms 12512 KB