Submission #229099
Source Code Expand
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <numeric> #include <cassert> #define FOR(i, min, max) for (int i = (min); i < (max); ++i) #define FORE(i, min, max) for (int i = (min); i <= (max); ++i) #define REP(i, n) for (int i = 0; i < (n); ++i) #define REPV(vec, i) for (int i = 0; i < (int)(vec.size()); ++i) #define FOR_EACH(vec, it) for (typeof((vec).begin()) it = (vec).begin(); it != (vec).end(); ++it) using namespace std; static const double EPS = 1e-12; typedef long long ll; ll mem[64][64][64][64]; /* [startx][starty][endx][endy] */ int W, H; int N; vector<pair<int, int> > P; int XtoIdx[1<<20]; int YtoIdx[1<<20]; ll solve(int sx, int sy, int ex, int ey) { if (sx > ex || sy > ey) { return 0; } ll &ret = mem[XtoIdx[sx]][YtoIdx[sy]][XtoIdx[ex]][YtoIdx[ey]]; if (ret < 0) { ret = 0; int sizex = (ex-sx+1); int sizey = (ey-sy+1); int numC = (sizex+sizey-1); REP(i, N) if (sx <= P[i].first && P[i].first <= ex && sy <= P[i].second && P[i].second <= ey) { ll n = numC; // left upper n += solve(sx, sy, P[i].first-1, P[i].second-1); // right upper n += solve(P[i].first+1, sy, ex, P[i].second-1); // left lower n += solve(sx, P[i].second+1, P[i].first-1, ey); // right lower n += solve(P[i].first+1, P[i].second+1, ex, ey); if (n > ret) { ret = n; } } //cout << "[DEBUG]: (" << sx << "," << sy << "),(" << ex << "," << ey << "): " << numC << "," << ret << endl; } return ret; } int main(void) { cin >> W >> H; cin >> N; P.resize(N); set<int> X; set<int> Y; X.insert(1); X.insert(W); Y.insert(1); Y.insert(H); REP(i, N) { cin >> P[i].first >> P[i].second; X.insert(P[i].first+1); X.insert(P[i].first-1); Y.insert(P[i].second+1); Y.insert(P[i].second-1); } memset(XtoIdx, -1, sizeof(XtoIdx)); memset(YtoIdx, -1, sizeof(YtoIdx)); int xidx = 0; for (set<int>::iterator it=X.begin(); it!=X.end(); it++) { XtoIdx[*it] = xidx++; } int yidx = 0; for (set<int>::iterator it=Y.begin(); it!=Y.end(); it++) { YtoIdx[*it] = yidx++; } memset(mem, -1, sizeof(mem)); ll ans = solve(1, 1, W, H); cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 金塊ゲーム |
User | imazato |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 2886 Byte |
Status | AC |
Exec Time | 323 ms |
Memory | 140076 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 80 / 80 | 19 / 19 | 1 / 1 | ||||||||
Status |
|
|
|
|
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 | 313 ms | 139940 KB |
sample_02.txt | AC | 313 ms | 140064 KB |
sample_03.txt | AC | 312 ms | 140068 KB |
subtask1_01.txt | AC | 315 ms | 139940 KB |
subtask1_02.txt | AC | 311 ms | 140064 KB |
subtask1_03.txt | AC | 310 ms | 139944 KB |
subtask1_04.txt | AC | 315 ms | 140072 KB |
subtask1_05.txt | AC | 311 ms | 140068 KB |
subtask1_06.txt | AC | 306 ms | 140064 KB |
subtask1_07.txt | AC | 286 ms | 140060 KB |
subtask1_08.txt | AC | 284 ms | 140064 KB |
subtask1_09.txt | AC | 287 ms | 140064 KB |
subtask1_10.txt | AC | 287 ms | 140068 KB |
subtask1_11.txt | AC | 317 ms | 140068 KB |
subtask1_12.txt | AC | 310 ms | 140068 KB |
subtask1_13.txt | AC | 312 ms | 140060 KB |
subtask1_14.txt | AC | 309 ms | 140056 KB |
subtask1_15.txt | AC | 314 ms | 140064 KB |
subtask1_16.txt | AC | 311 ms | 140056 KB |
subtask1_17.txt | AC | 313 ms | 140064 KB |
subtask1_18.txt | AC | 313 ms | 139936 KB |
subtask1_19.txt | AC | 313 ms | 139944 KB |
subtask1_20.txt | AC | 309 ms | 140076 KB |
subtask1_21.txt | AC | 311 ms | 139940 KB |
subtask1_22.txt | AC | 312 ms | 140008 KB |
subtask1_23.txt | AC | 307 ms | 140068 KB |
subtask1_24.txt | AC | 289 ms | 140064 KB |
subtask1_25.txt | AC | 308 ms | 139992 KB |
subtask2_01.txt | AC | 285 ms | 140072 KB |
subtask2_02.txt | AC | 307 ms | 140064 KB |
subtask2_03.txt | AC | 312 ms | 140068 KB |
subtask2_04.txt | AC | 312 ms | 139940 KB |
subtask2_05.txt | AC | 308 ms | 139936 KB |
subtask2_06.txt | AC | 293 ms | 140000 KB |
subtask2_07.txt | AC | 291 ms | 140056 KB |
subtask2_08.txt | AC | 289 ms | 140064 KB |
subtask2_09.txt | AC | 293 ms | 140064 KB |
subtask2_10.txt | AC | 291 ms | 140064 KB |
subtask2_11.txt | AC | 291 ms | 140060 KB |
subtask2_12.txt | AC | 294 ms | 140060 KB |
subtask2_13.txt | AC | 288 ms | 140060 KB |
subtask2_14.txt | AC | 289 ms | 140064 KB |
subtask2_15.txt | AC | 314 ms | 139996 KB |
subtask2_16.txt | AC | 314 ms | 139996 KB |
subtask2_17.txt | AC | 291 ms | 140060 KB |
subtask2_18.txt | AC | 291 ms | 140060 KB |
subtask2_19.txt | AC | 292 ms | 140052 KB |
subtask2_20.txt | AC | 317 ms | 139996 KB |
subtask2_21.txt | AC | 317 ms | 139996 KB |
subtask2_22.txt | AC | 293 ms | 140064 KB |
subtask2_23.txt | AC | 303 ms | 140068 KB |
subtask2_24.txt | AC | 318 ms | 140064 KB |
subtask2_25.txt | AC | 319 ms | 140064 KB |
subtask3_01.txt | AC | 311 ms | 140060 KB |
subtask3_02.txt | AC | 314 ms | 140064 KB |
subtask3_03.txt | AC | 308 ms | 140060 KB |
subtask3_04.txt | AC | 299 ms | 140060 KB |
subtask3_05.txt | AC | 306 ms | 140064 KB |
subtask3_06.txt | AC | 288 ms | 140064 KB |
subtask3_07.txt | AC | 285 ms | 140072 KB |
subtask3_08.txt | AC | 289 ms | 140060 KB |
subtask3_09.txt | AC | 291 ms | 140060 KB |
subtask3_10.txt | AC | 320 ms | 140064 KB |
subtask3_11.txt | AC | 295 ms | 140000 KB |
subtask3_12.txt | AC | 287 ms | 140064 KB |
subtask3_13.txt | AC | 293 ms | 140068 KB |
subtask3_14.txt | AC | 287 ms | 140068 KB |
subtask3_15.txt | AC | 301 ms | 140064 KB |
subtask3_16.txt | AC | 308 ms | 140068 KB |
subtask3_17.txt | AC | 290 ms | 140060 KB |
subtask3_18.txt | AC | 289 ms | 140060 KB |
subtask3_19.txt | AC | 287 ms | 140068 KB |
subtask3_20.txt | AC | 290 ms | 140056 KB |
subtask3_21.txt | AC | 291 ms | 140064 KB |
subtask3_22.txt | AC | 295 ms | 140060 KB |
subtask3_23.txt | AC | 323 ms | 140036 KB |
subtask3_24.txt | AC | 296 ms | 140064 KB |
subtask3_25.txt | AC | 292 ms | 140056 KB |