Submission #588743


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

#define whole(xs) xs.begin(), xs.end()
#define uniq(xs) (xs.erase(unique(xs.begin(), xs.end()), xs.end()))

namespace {
    typedef long long ll;

    template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) {
        if (vs.empty()) return os << "[]";
        os << "[" << vs[0];
        for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
        return os << "]";
    }

    int W, H;
    int N;
    vector<int> X, Y;
    void input() {
        cin >> W >> H >> N;
        X.clear(); X.resize(N);
        Y.clear(); Y.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> X[i] >> Y[i];
            X[i]--; Y[i]--;
        }
    }

    map< tuple<int, int, int, int>, ll > memo;
    ll calc(int sy, int sx, int gy, int gx) {
        auto key = make_tuple(sy, sx, gy, gx);
        if (memo.count(key)) return memo[key];

        vector<int> xs, ys;
        for (int i = 0; i < N; i++) {
            int x = X[i], y = Y[i];
            if (sx <= x && x < gx && sy <= y && y < gy) {
                xs.push_back(x);
                ys.push_back(y);
            }
        }

        ll ans = 0;
        for (int i = 0; i < xs.size(); i++) {
            int x = xs[i], y = ys[i];
            ans = max(ans, 
                    calc(sy, sx, y, x) + 
                    calc(y + 1, sx, gy, x) + 
                    calc(sy, x + 1, y, gx) + 
                    calc(y + 1, x + 1, gy, gx) + 
                    (gy - sy) + (gx - sx) - 1);
        }
        return memo[key] = ans;
    }

    void solve() {
        cout << calc(0, 0, H, W) << endl;
    }
}

int main() {
    input(); solve();
    return 0;
}

Submission Info

Submission Time
Task D - 金塊ゲーム
User izuru
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1756 Byte
Status AC
Exec Time 68 ms
Memory 1616 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 27 ms 944 KB
sample_02.txt AC 24 ms 948 KB
sample_03.txt AC 24 ms 1048 KB
subtask1_01.txt AC 26 ms 1044 KB
subtask1_02.txt AC 26 ms 856 KB
subtask1_03.txt AC 25 ms 1044 KB
subtask1_04.txt AC 25 ms 1040 KB
subtask1_05.txt AC 24 ms 856 KB
subtask1_06.txt AC 25 ms 1044 KB
subtask1_07.txt AC 24 ms 1048 KB
subtask1_08.txt AC 25 ms 1048 KB
subtask1_09.txt AC 27 ms 856 KB
subtask1_10.txt AC 27 ms 1052 KB
subtask1_11.txt AC 25 ms 1048 KB
subtask1_12.txt AC 25 ms 964 KB
subtask1_13.txt AC 25 ms 1044 KB
subtask1_14.txt AC 25 ms 876 KB
subtask1_15.txt AC 24 ms 1044 KB
subtask1_16.txt AC 24 ms 1044 KB
subtask1_17.txt AC 25 ms 872 KB
subtask1_18.txt AC 26 ms 1044 KB
subtask1_19.txt AC 24 ms 1048 KB
subtask1_20.txt AC 25 ms 1048 KB
subtask1_21.txt AC 26 ms 1052 KB
subtask1_22.txt AC 25 ms 1044 KB
subtask1_23.txt AC 24 ms 1044 KB
subtask1_24.txt AC 28 ms 952 KB
subtask1_25.txt AC 24 ms 1040 KB
subtask2_01.txt AC 27 ms 948 KB
subtask2_02.txt AC 27 ms 996 KB
subtask2_03.txt AC 33 ms 1176 KB
subtask2_04.txt AC 33 ms 1080 KB
subtask2_05.txt AC 39 ms 1208 KB
subtask2_06.txt AC 43 ms 1332 KB
subtask2_07.txt AC 44 ms 1336 KB
subtask2_08.txt AC 44 ms 1328 KB
subtask2_09.txt AC 64 ms 1584 KB
subtask2_10.txt AC 62 ms 1592 KB
subtask2_11.txt AC 63 ms 1588 KB
subtask2_12.txt AC 65 ms 1592 KB
subtask2_13.txt AC 45 ms 1332 KB
subtask2_14.txt AC 43 ms 1336 KB
subtask2_15.txt AC 28 ms 992 KB
subtask2_16.txt AC 50 ms 1332 KB
subtask2_17.txt AC 66 ms 1588 KB
subtask2_18.txt AC 67 ms 1592 KB
subtask2_19.txt AC 64 ms 1592 KB
subtask2_20.txt AC 63 ms 1584 KB
subtask2_21.txt AC 66 ms 1588 KB
subtask2_22.txt AC 62 ms 1588 KB
subtask2_23.txt AC 64 ms 1592 KB
subtask2_24.txt AC 65 ms 1592 KB
subtask2_25.txt AC 68 ms 1596 KB
subtask3_01.txt AC 26 ms 1044 KB
subtask3_02.txt AC 27 ms 992 KB
subtask3_03.txt AC 29 ms 980 KB
subtask3_04.txt AC 32 ms 1044 KB
subtask3_05.txt AC 37 ms 1208 KB
subtask3_06.txt AC 34 ms 1076 KB
subtask3_07.txt AC 34 ms 1072 KB
subtask3_08.txt AC 44 ms 1336 KB
subtask3_09.txt AC 47 ms 1332 KB
subtask3_10.txt AC 67 ms 1496 KB
subtask3_11.txt AC 62 ms 1588 KB
subtask3_12.txt AC 67 ms 1516 KB
subtask3_13.txt AC 66 ms 1588 KB
subtask3_14.txt AC 62 ms 1500 KB
subtask3_15.txt AC 64 ms 1592 KB
subtask3_16.txt AC 64 ms 1616 KB
subtask3_17.txt AC 65 ms 1588 KB
subtask3_18.txt AC 39 ms 1212 KB
subtask3_19.txt AC 62 ms 1592 KB
subtask3_20.txt AC 45 ms 1336 KB
subtask3_21.txt AC 67 ms 1584 KB
subtask3_22.txt AC 66 ms 1584 KB
subtask3_23.txt AC 66 ms 1584 KB
subtask3_24.txt AC 65 ms 1592 KB
subtask3_25.txt AC 62 ms 1592 KB