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
Task D - 金塊ゲーム
User izuru
Language C++ (G++ 4.6.4)
Score 0
Code Size 2707 Byte
Status RE
Exec Time 679 ms
Memory 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

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