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
Task D - 金塊ゲーム
User zerokugi
Language C++ (G++ 4.6.4)
Score 100
Code Size 1703 Byte
Status AC
Exec Time 69 ms
Memory 12592 KB

Judge Result

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