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

Submission #169509

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<ll> p;
vector<int> X;
vector<int> Y;

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

ll memo[31][31][31][31];

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 >> 30];
int y = toY[*it & ((1<<30)-1)];
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((x<<30)|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:04:53+0900 D - 金塊ゲーム zerokugi C++ (G++ 4.6.4) 80 1709 Byte RE 340 ms 8092 KB

#### Judge Result

Score / Max Score 0 / 0 80 / 80 0 / 19 0 / 1
Status
 AC × 3
 AC × 25
 AC × 37 RE × 13
 AC × 48 RE × 27
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt AC 36 ms 7980 KB
sample_02.txt AC 34 ms 7968 KB
sample_03.txt AC 32 ms 7968 KB
subtask1_01.txt AC 35 ms 7976 KB
subtask1_02.txt AC 33 ms 7968 KB
subtask1_03.txt AC 33 ms 8072 KB
subtask1_04.txt AC 34 ms 7984 KB
subtask1_05.txt AC 33 ms 7976 KB
subtask1_06.txt AC 33 ms 8080 KB
subtask1_07.txt AC 32 ms 7980 KB
subtask1_08.txt AC 32 ms 7976 KB
subtask1_09.txt AC 32 ms 7968 KB
subtask1_10.txt AC 34 ms 7972 KB
subtask1_11.txt AC 34 ms 8080 KB
subtask1_12.txt AC 32 ms 7976 KB
subtask1_13.txt AC 34 ms 7968 KB
subtask1_14.txt AC 35 ms 7976 KB
subtask1_15.txt AC 33 ms 8092 KB
subtask1_16.txt AC 34 ms 7980 KB
subtask1_17.txt AC 36 ms 7972 KB
subtask1_18.txt AC 33 ms 7972 KB
subtask1_19.txt AC 34 ms 7972 KB
subtask1_20.txt AC 35 ms 8088 KB
subtask1_21.txt AC 34 ms 7980 KB
subtask1_22.txt AC 33 ms 7980 KB
subtask1_23.txt AC 33 ms 7972 KB
subtask1_24.txt AC 36 ms 8000 KB
subtask1_25.txt AC 33 ms 7980 KB
subtask2_01.txt AC 34 ms 7980 KB
subtask2_02.txt AC 39 ms 7980 KB
subtask2_03.txt AC 36 ms 7972 KB
subtask2_04.txt AC 37 ms 7976 KB
subtask2_05.txt AC 41 ms 7968 KB
subtask2_06.txt AC 45 ms 7984 KB
subtask2_07.txt AC 43 ms 8088 KB
subtask2_08.txt AC 44 ms 7980 KB
subtask2_09.txt RE 340 ms 7972 KB
subtask2_10.txt RE 254 ms 7984 KB
subtask2_11.txt RE 257 ms 7976 KB
subtask2_12.txt RE 249 ms 7972 KB
subtask2_13.txt AC 43 ms 7976 KB
subtask2_14.txt AC 44 ms 7984 KB
subtask2_15.txt AC 34 ms 8088 KB
subtask2_16.txt AC 44 ms 7980 KB
subtask2_17.txt RE 250 ms 7976 KB
subtask2_18.txt RE 247 ms 7964 KB
subtask2_19.txt RE 246 ms 7968 KB
subtask2_20.txt RE 258 ms 7980 KB
subtask2_21.txt RE 250 ms 7976 KB
subtask2_22.txt RE 249 ms 7972 KB
subtask2_23.txt RE 250 ms 7972 KB
subtask2_24.txt RE 247 ms 7972 KB
subtask2_25.txt RE 255 ms 7984 KB
subtask3_01.txt AC 34 ms 7976 KB
subtask3_02.txt AC 35 ms 7972 KB
subtask3_03.txt AC 34 ms 7968 KB
subtask3_04.txt AC 37 ms 7972 KB
subtask3_05.txt AC 41 ms 7980 KB
subtask3_06.txt AC 37 ms 8060 KB
subtask3_07.txt AC 37 ms 7972 KB
subtask3_08.txt AC 42 ms 7980 KB
subtask3_09.txt AC 44 ms 7972 KB
subtask3_10.txt RE 247 ms 8060 KB
subtask3_11.txt RE 245 ms 7976 KB
subtask3_12.txt RE 255 ms 7972 KB
subtask3_13.txt RE 253 ms 7972 KB
subtask3_14.txt RE 258 ms 7976 KB
subtask3_15.txt RE 254 ms 7976 KB
subtask3_16.txt RE 252 ms 7972 KB
subtask3_17.txt RE 259 ms 7976 KB
subtask3_18.txt AC 41 ms 7980 KB
subtask3_19.txt RE 259 ms 8060 KB
subtask3_20.txt AC 44 ms 7980 KB
subtask3_21.txt RE 253 ms 7980 KB
subtask3_22.txt RE 265 ms 7980 KB
subtask3_23.txt RE 255 ms 7980 KB
subtask3_24.txt RE 245 ms 7976 KB
subtask3_25.txt RE 251 ms 7980 KB