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