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
Task D - 金塊ゲーム
User zerokugi
Language C++ (G++ 4.6.4)
Score 80
Code Size 1709 Byte
Status RE
Exec Time 340 ms
Memory 8092 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
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
Subtask1 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 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 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 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