Submission #169752


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];

void Copy(bool** src, bool dst[81][81]) {
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            dst[i][j] = src[i][j];
        }
    }
}
void Copy(bool src[81][81], bool** dst) {
    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            dst[i][j] = src[i][j];
        }
    }
}

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;
    bool** G = new bool*[W];
    for (int i = 0; i < W; i++) G[i] = new bool[H];
    for (int i = 0; i < N; i++) {
        if (bit & (1 << i)) {
            Copy(F, 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);
            Copy(G, F);
        }
    }
    for (int i = 0; i < W; i++) delete[] G[i]; delete[] 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 99
Code Size 3156 Byte
Status MLE
Exec Time 1922 ms
Memory 569636 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 80 / 80 19 / 19 0 / 1
Status
AC × 3
AC × 25
AC × 50
AC × 50
MLE × 2
RE × 23
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 276 ms 168948 KB
sample_02.txt AC 300 ms 168872 KB
sample_03.txt AC 277 ms 168864 KB
subtask1_01.txt AC 279 ms 168868 KB
subtask1_02.txt AC 255 ms 168864 KB
subtask1_03.txt AC 256 ms 168876 KB
subtask1_04.txt AC 302 ms 168860 KB
subtask1_05.txt AC 280 ms 168868 KB
subtask1_06.txt AC 273 ms 168988 KB
subtask1_07.txt AC 284 ms 168944 KB
subtask1_08.txt AC 291 ms 168864 KB
subtask1_09.txt AC 297 ms 168868 KB
subtask1_10.txt AC 279 ms 168884 KB
subtask1_11.txt AC 292 ms 168860 KB
subtask1_12.txt AC 259 ms 168872 KB
subtask1_13.txt AC 260 ms 168876 KB
subtask1_14.txt AC 276 ms 168996 KB
subtask1_15.txt AC 272 ms 168988 KB
subtask1_16.txt AC 285 ms 168872 KB
subtask1_17.txt AC 293 ms 168868 KB
subtask1_18.txt AC 304 ms 168872 KB
subtask1_19.txt AC 260 ms 168868 KB
subtask1_20.txt AC 303 ms 168872 KB
subtask1_21.txt AC 309 ms 168864 KB
subtask1_22.txt AC 287 ms 168936 KB
subtask1_23.txt AC 267 ms 168860 KB
subtask1_24.txt AC 267 ms 168872 KB
subtask1_25.txt AC 267 ms 168948 KB
subtask2_01.txt AC 263 ms 168868 KB
subtask2_02.txt AC 285 ms 168872 KB
subtask2_03.txt AC 291 ms 168876 KB
subtask2_04.txt AC 348 ms 168988 KB
subtask2_05.txt AC 366 ms 168988 KB
subtask2_06.txt AC 352 ms 168996 KB
subtask2_07.txt AC 315 ms 168860 KB
subtask2_08.txt AC 346 ms 168876 KB
subtask2_09.txt AC 503 ms 169000 KB
subtask2_10.txt AC 612 ms 168988 KB
subtask2_11.txt AC 381 ms 168864 KB
subtask2_12.txt AC 642 ms 168992 KB
subtask2_13.txt AC 445 ms 168992 KB
subtask2_14.txt AC 428 ms 168992 KB
subtask2_15.txt AC 297 ms 168992 KB
subtask2_16.txt AC 348 ms 168864 KB
subtask2_17.txt AC 426 ms 168876 KB
subtask2_18.txt AC 540 ms 168996 KB
subtask2_19.txt AC 506 ms 169000 KB
subtask2_20.txt AC 483 ms 168996 KB
subtask2_21.txt AC 500 ms 168996 KB
subtask2_22.txt AC 534 ms 169000 KB
subtask2_23.txt AC 535 ms 168996 KB
subtask2_24.txt AC 643 ms 168996 KB
subtask2_25.txt AC 667 ms 169004 KB
subtask3_01.txt RE 514 ms 168948 KB
subtask3_02.txt RE 1650 ms 489504 KB
subtask3_03.txt RE 502 ms 168996 KB
subtask3_04.txt RE 519 ms 168920 KB
subtask3_05.txt RE 534 ms 168992 KB
subtask3_06.txt RE 523 ms 168868 KB
subtask3_07.txt RE 503 ms 169120 KB
subtask3_08.txt RE 509 ms 168868 KB
subtask3_09.txt RE 477 ms 168948 KB
subtask3_10.txt RE 504 ms 169052 KB
subtask3_11.txt RE 520 ms 168868 KB
subtask3_12.txt RE 500 ms 174876 KB
subtask3_13.txt RE 527 ms 168864 KB
subtask3_14.txt RE 522 ms 168868 KB
subtask3_15.txt RE 521 ms 169260 KB
subtask3_16.txt RE 487 ms 168976 KB
subtask3_17.txt RE 525 ms 168872 KB
subtask3_18.txt RE 530 ms 169244 KB
subtask3_19.txt RE 537 ms 168872 KB
subtask3_20.txt RE 513 ms 169056 KB
subtask3_21.txt MLE 1188 ms 569636 KB
subtask3_22.txt MLE 1922 ms 569636 KB
subtask3_23.txt RE 535 ms 168864 KB
subtask3_24.txt RE 499 ms 168856 KB
subtask3_25.txt RE 537 ms 168876 KB