Submission #4015626


Source Code Expand

/* ---------- STL Libraries ---------- */

// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */

using namespace std;

/* ---------- Type Abbreviation ---------- */

using ll = long long;

template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

#define mp make_pair
#define mt make_tuple

/* ----------- debug ---------- */

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p);

template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class T>
ostream& operator<<(ostream& os, set<T> v) {
    os << "[";
    for (auto vv : v)
        os << vv << ",";
    return os << "]";
}

template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> p) {
    return os << "(" << p.first << "," << p.second << ")";
}

/* ---------- Constants ---------- */

// const ll MOD = 1000000007;
// const ll MOD = 998244353;
// const int INF = 1 << 25;
// const ll INF = 1LL << 50;
// const double PI = acos(-1);
// const double EPS = 1e-10;
// mt19937 mert(LL(time(0)));

/* ---------- Short Functions ---------- */

template <typename T>
inline T sq(T a) { return a * a; }

template <typename T>
T gcd(T a, T b) {
    if (a > b) return gcd(b, a);
    return a == 0 ? b : gcd(b % a, a);
}

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b /* % MOD */;
    if (n % 2 == 0) {
        return mypow(b * b /* % MOD */, n / 2);
    } else {
        return mypow(b, n - 1) * b /* % MOD */;
    }
}

ll pcnt(ll b) {
    return __builtin_popcountll(b);
}

template <typename T>
T iceil(T n, T d) {
    return (n + d - 1) / d;
}

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */

int H, W, N, X[30], Y[30];
int dp[80][80][80][80];
bool visited[80][80][80][80];

int rec(int lx, int ly, int ux, int uy) {
    if (ux < lx || uy < ly) return 0;

    if (visited[lx][ly][ux][uy]) return dp[lx][ly][ux][uy];
    visited[lx][ly][ux][uy] = true;

    dp[lx][ly][ux][uy] = 0;
    int cross = (ux - lx) + (uy - ly) + 1;

    for (int i = 0; i < N; ++i) {
        if (X[i] < lx || ux < X[i] || Y[i] < ly || uy < Y[i]) continue;
        int res = 0;
        res += rec(lx, ly, X[i] - 1, Y[i] - 1);
        res += rec(X[i] + 1, ly, ux, Y[i] - 1);
        res += rec(lx, Y[i] + 1, X[i] - 1, uy);
        res += rec(X[i] + 1, Y[i] + 1, ux, uy);
        dp[lx][ly][ux][uy] = max(dp[lx][ly][ux][uy], res + cross);
    }

    return dp[lx][ly][ux][uy];
}

int main() {
    cin >> H >> W >> N;
    if (H * W > 6400) terminate();

    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> Y[i];
        --X[i], --Y[i];
    }

    cout << rec(0, 0, H - 1, W - 1) << endl;
    return 0;
}

Submission Info

Submission Time
Task D - 金塊ゲーム
User Tiramister
Language C++14 (GCC 5.4.1)
Score 99
Code Size 3320 Byte
Status RE
Exec Time 109 ms
Memory 137984 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
RE × 25
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 4 ms 8448 KB
sample_02.txt AC 3 ms 6400 KB
sample_03.txt AC 7 ms 22912 KB
subtask1_01.txt AC 4 ms 10496 KB
subtask1_02.txt AC 3 ms 6400 KB
subtask1_03.txt AC 6 ms 18816 KB
subtask1_04.txt AC 8 ms 26880 KB
subtask1_05.txt AC 6 ms 16640 KB
subtask1_06.txt AC 4 ms 8448 KB
subtask1_07.txt AC 6 ms 16640 KB
subtask1_08.txt AC 2 ms 2304 KB
subtask1_09.txt AC 11 ms 35072 KB
subtask1_10.txt AC 5 ms 16640 KB
subtask1_11.txt AC 8 ms 26880 KB
subtask1_12.txt AC 5 ms 14720 KB
subtask1_13.txt AC 9 ms 28928 KB
subtask1_14.txt AC 11 ms 37120 KB
subtask1_15.txt AC 13 ms 45312 KB
subtask1_16.txt AC 9 ms 28928 KB
subtask1_17.txt AC 9 ms 30976 KB
subtask1_18.txt AC 6 ms 18816 KB
subtask1_19.txt AC 7 ms 18816 KB
subtask1_20.txt AC 10 ms 18816 KB
subtask1_21.txt AC 10 ms 35072 KB
subtask1_22.txt AC 11 ms 35200 KB
subtask1_23.txt AC 6 ms 18816 KB
subtask1_24.txt AC 12 ms 41344 KB
subtask1_25.txt AC 15 ms 47488 KB
subtask2_01.txt AC 13 ms 43520 KB
subtask2_02.txt AC 13 ms 39424 KB
subtask2_03.txt AC 21 ms 67968 KB
subtask2_04.txt AC 29 ms 96768 KB
subtask2_05.txt AC 29 ms 94848 KB
subtask2_06.txt AC 25 ms 80512 KB
subtask2_07.txt AC 23 ms 74368 KB
subtask2_08.txt AC 24 ms 76288 KB
subtask2_09.txt AC 33 ms 107392 KB
subtask2_10.txt AC 39 ms 129792 KB
subtask2_11.txt AC 29 ms 91008 KB
subtask2_12.txt AC 41 ms 133760 KB
subtask2_13.txt AC 37 ms 127488 KB
subtask2_14.txt AC 36 ms 123520 KB
subtask2_15.txt AC 18 ms 61824 KB
subtask2_16.txt AC 25 ms 78464 KB
subtask2_17.txt AC 26 ms 82304 KB
subtask2_18.txt AC 36 ms 119424 KB
subtask2_19.txt AC 35 ms 113408 KB
subtask2_20.txt AC 33 ms 105216 KB
subtask2_21.txt AC 32 ms 103168 KB
subtask2_22.txt AC 37 ms 121600 KB
subtask2_23.txt AC 38 ms 127360 KB
subtask2_24.txt AC 42 ms 137984 KB
subtask2_25.txt AC 39 ms 125696 KB
subtask3_01.txt RE 99 ms 2304 KB
subtask3_02.txt RE 103 ms 14592 KB
subtask3_03.txt RE 103 ms 256 KB
subtask3_04.txt RE 100 ms 256 KB
subtask3_05.txt RE 104 ms 256 KB
subtask3_06.txt RE 102 ms 2304 KB
subtask3_07.txt RE 109 ms 256 KB
subtask3_08.txt RE 104 ms 256 KB
subtask3_09.txt RE 101 ms 2304 KB
subtask3_10.txt RE 99 ms 256 KB
subtask3_11.txt RE 105 ms 2304 KB
subtask3_12.txt RE 103 ms 256 KB
subtask3_13.txt RE 104 ms 2304 KB
subtask3_14.txt RE 105 ms 256 KB
subtask3_15.txt RE 102 ms 256 KB
subtask3_16.txt RE 104 ms 256 KB
subtask3_17.txt RE 100 ms 2304 KB
subtask3_18.txt RE 104 ms 256 KB
subtask3_19.txt RE 105 ms 2304 KB
subtask3_20.txt RE 103 ms 256 KB
subtask3_21.txt RE 102 ms 256 KB
subtask3_22.txt RE 101 ms 256 KB
subtask3_23.txt RE 103 ms 2304 KB
subtask3_24.txt RE 105 ms 2304 KB
subtask3_25.txt RE 103 ms 2304 KB