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

Submission #169716

Source Code Expand

Copy
```#include <cstdio>
#include <cstring>
#include <cassert>
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <queue>
#include <utility>

using namespace std;
#define whole(xs) xs.begin(), xs.end()

struct P {
int x, y;
P(int x, int y) : x(x), y(y) {}
};
bool operator<(const P& a, const P& b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}

int Fire(int i);

int W, H;
int N;
vector<P> Ps;

#define MW 81
#define MH 81
bool F[MW][MH];

int BIT(int sx, int sy, int gx, int gy) {
int ret = 0;
for (int i = 0; i < N; i++) {
const P& p = Ps[i];
if (sx <= p.x && p.x < gx && sy <= p.y && p.y < gy) {
ret |= (1 << i);
}
}
return ret;
}

int memo[MW][MH][MW][MH];
int Calc(int bit, int sx, int sy, int gx, int gy) {
if (bit == 0) return 0;
if (memo[sx][sy][gx][gy] >= 0) return memo[sx][sy][gx][gy];
int Ans = 0;
int G[MW][MH];
for (int i = 0; i < N; i++) {
if (bit & (1 << i)) {
memcpy(G, F, sizeof(G));
int Count = Fire(i);
int x = Ps[i].x,
y = Ps[i].y;
Count += Calc(BIT(sx, sy, x, y), sx, sy, x, y);
Count += Calc(BIT(sx, y + 1, x, gy), sx, y + 1, x, gy);
Count += Calc(BIT(x + 1, sy, gx, y), x + 1, sy, gx, y);
Count += Calc(BIT(x + 1, y + 1, gx, gy), x + 1, y + 1, gx, gy);
Ans = max(Ans, Count);
memcpy(F, G, sizeof(G));
}
}
return memo[sx][sy][gx][gy] = Ans;
}

int Fire(int i) {
int Count = 0;
int x = Ps[i].x;
int y = Ps[i].y;
for (int a = y + 1; a < H && F[x][a]; a++) {
Count++;
F[x][a] = false;
}
for (int a = y - 1; a >= 0 && F[x][a]; a--) {
Count++;
F[x][a] = false;
}
for (int a = x + 1; a < W && F[a][y]; a++) {
Count++;
F[a][y] = false;
}
for (int a = x - 1; a >= 0 && F[a][y]; a--) {
Count++;
F[a][y] = false;
}
Count++;
F[x][y] = false;
/*
for (int i = 0; i < W; i++) {
for (int j = 0; j < H; j++) {
cout << setw(1) << F[i][j];
}
cout << endl;
}
cout << endl;
*/
return Count;
}

int main() {
cin >> W >> H >> N;
for (int i = 0; i < N; i++) {
int X, Y;
cin >> X >> Y;
X--; Y--;
Ps.push_back(P(X, Y));
}
memset(memo, -1, sizeof(memo));
memset(F, 1, sizeof(F));
cout << Calc((1 << N) - 1, 0, 0, W, H) << endl;
return 0;
}
```

#### Submission Info

Submission Time 2014-05-10 22:34:57+0900 D - 金塊ゲーム izuru C++ (G++ 4.6.4) 0 2707 Byte RE 679 ms 168996 KB

#### Compile Error

```In file included from /usr/include/string.h:642:0,
from /usr/include/c++/4.6/cstring:44,
from ./Main.cpp:2:
In function ‘void* memcpy(void*, const void*, size_t)’,
inlined from ‘int Calc(int, int, int, int, int)’ at ./Main.cpp:63:36:
/usr/include/x86_64-linux-gnu/bits/string3.h:52:71: warning: call to void* __builtin___memcpy_chk(void*, const void*, long unsigned int, long unsigned int) will always overflow destination buffer [enabled by default]
```

#### Judge Result

Score / Max Score 0 / 0 0 / 80 0 / 19 0 / 1
Status
 RE × 3
 RE × 25
 RE × 50
 RE × 75
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt RE 679 ms 168872 KB
sample_02.txt RE 542 ms 168880 KB
sample_03.txt RE 561 ms 168872 KB
subtask1_01.txt RE 563 ms 168880 KB
subtask1_02.txt RE 559 ms 168864 KB
subtask1_03.txt RE 540 ms 168856 KB
subtask1_04.txt RE 540 ms 168872 KB
subtask1_05.txt RE 520 ms 168948 KB
subtask1_06.txt RE 491 ms 168944 KB
subtask1_07.txt RE 541 ms 168992 KB
subtask1_08.txt RE 510 ms 168860 KB
subtask1_09.txt RE 517 ms 168876 KB
subtask1_10.txt RE 539 ms 168924 KB
subtask1_11.txt RE 539 ms 168872 KB
subtask1_12.txt RE 545 ms 168872 KB
subtask1_13.txt RE 487 ms 168948 KB
subtask1_14.txt RE 501 ms 168868 KB
subtask1_15.txt RE 512 ms 168868 KB
subtask1_16.txt RE 525 ms 168872 KB
subtask1_17.txt RE 495 ms 168860 KB
subtask1_18.txt RE 510 ms 168872 KB
subtask1_19.txt RE 529 ms 168936 KB
subtask1_20.txt RE 484 ms 168868 KB
subtask1_21.txt RE 508 ms 168864 KB
subtask1_22.txt RE 497 ms 168992 KB
subtask1_23.txt RE 510 ms 168876 KB
subtask1_24.txt RE 530 ms 168996 KB
subtask1_25.txt RE 485 ms 168872 KB
subtask2_01.txt RE 541 ms 168864 KB
subtask2_02.txt RE 498 ms 168844 KB
subtask2_03.txt RE 501 ms 168868 KB
subtask2_04.txt RE 499 ms 168872 KB
subtask2_05.txt RE 529 ms 168868 KB
subtask2_06.txt RE 542 ms 168868 KB
subtask2_07.txt RE 499 ms 168860 KB
subtask2_08.txt RE 538 ms 168872 KB
subtask2_09.txt RE 490 ms 168876 KB
subtask2_10.txt RE 487 ms 168868 KB
subtask2_11.txt RE 482 ms 168864 KB
subtask2_12.txt RE 543 ms 168864 KB
subtask2_13.txt RE 489 ms 168860 KB
subtask2_14.txt RE 524 ms 168876 KB
subtask2_15.txt RE 528 ms 168864 KB
subtask2_16.txt RE 480 ms 168868 KB
subtask2_17.txt RE 498 ms 168872 KB
subtask2_18.txt RE 512 ms 168856 KB
subtask2_19.txt RE 490 ms 168916 KB
subtask2_20.txt RE 541 ms 168996 KB
subtask2_21.txt RE 498 ms 168860 KB
subtask2_22.txt RE 536 ms 168948 KB
subtask2_23.txt RE 543 ms 168868 KB
subtask2_24.txt RE 494 ms 168876 KB
subtask2_25.txt RE 487 ms 168984 KB
subtask3_01.txt RE 485 ms 168868 KB
subtask3_02.txt RE 534 ms 168860 KB
subtask3_03.txt RE 515 ms 168868 KB
subtask3_04.txt RE 513 ms 168872 KB
subtask3_05.txt RE 526 ms 168868 KB
subtask3_06.txt RE 490 ms 168860 KB
subtask3_07.txt RE 527 ms 168864 KB
subtask3_08.txt RE 512 ms 168872 KB
subtask3_09.txt RE 535 ms 168936 KB
subtask3_10.txt RE 505 ms 168924 KB
subtask3_11.txt RE 514 ms 168924 KB
subtask3_12.txt RE 490 ms 168868 KB
subtask3_13.txt RE 498 ms 168868 KB
subtask3_14.txt RE 479 ms 168872 KB
subtask3_15.txt RE 532 ms 168948 KB
subtask3_16.txt RE 488 ms 168864 KB
subtask3_17.txt RE 492 ms 168872 KB
subtask3_18.txt RE 507 ms 168992 KB
subtask3_19.txt RE 536 ms 168872 KB
subtask3_20.txt RE 520 ms 168864 KB
subtask3_21.txt RE 536 ms 168868 KB
subtask3_22.txt RE 541 ms 168856 KB
subtask3_23.txt RE 538 ms 168868 KB
subtask3_24.txt RE 507 ms 168876 KB
subtask3_25.txt RE 505 ms 168876 KB