Submission #1584965
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);
template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
each(x,vec) is >> x;
return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
rep(i,vec.size()) {
if (i) os << " ";
os << vec[i];
}
return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
rep(i,vec.size()) {
if (i) os << endl;
os << vec[i];
}
return os;
}
map<ll, ll> compress(vector<ll>& X) {
map<ll, ll> res;
sort(all(X));
X.erase(unique(all(X)), X.end());
rep(i, X.size()) res[X[i]] = i;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll w, h; cin >> w >> h;
vector<ll> X{0, w}, Y{0, h};
ll n; cin >> n;
vector<P> v;
rep(i, n) {
ll x, y; cin >> x >> y; --x, --y;
v.pb({x, y});
rep(j, -1, 2) {
ll nx = x + j;
ll ny = y + j;
if (0 <= nx && nx <= w) X.pb(nx);
if (0 <= ny && ny <= h) Y.pb(ny);
}
}
map<ll, ll> xto = compress(X);
map<ll, ll> yto = compress(Y);
each(p, v) {
p.first = xto[p.first];
p.second = yto[p.second];
// cout << "-> " << p.first << " " << p.second << endl;
}
w = xto.size();
h = yto.size();
vector<vector<vector<vector<bool>>>> m1(w, vector<vector<vector<bool>>>(h, vector<vector<bool>>(w+1, vector<bool>(h+1, false))));
vector<vector<vector<vector<ll>>>> m2(w, vector<vector<vector<ll>>>(h, vector<vector<ll>>(w+1, vector<ll>(h+1))));
function<ll(ll,ll,ll,ll)> dp = [&](ll x1, ll y1, ll x2, ll y2) {
if (m1[x1][y1][x2][y2]) return m2[x1][y1][x2][y2];
ll res = 0;
rep(i, n) {
ll x, y; tie(x, y) = v[i];
if (x < x1 || x2 <= x || y < y1 || y2 <= y) continue;
// cout << x << " " << y << endl;
chmax(res,
(X[x2]-X[x1])+(Y[y2]-Y[y1])-1
+ dp(x1, y1, x, y)
+ dp(x+1, y1, x2, y)
+ dp(x1, y+1, x, y2)
+ dp(x+1, y+1, x2, y2));
}
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << " : " << res << endl;
return m1[x1][y1][x2][y2] = true, m2[x1][y1][x2][y2] = res;
};
cout << dp(0, 0, w-1, h-1) << endl;
}
Submission Info
Submission Time |
|
Task |
D - 金塊ゲーム |
User |
drafear |
Language |
C++14 (GCC 5.4.1) |
Score |
99 |
Code Size |
3166 Byte |
Status |
MLE |
Exec Time |
434 ms |
Memory |
659200 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 |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
2 ms |
768 KB |
subtask1_01.txt |
AC |
1 ms |
384 KB |
subtask1_02.txt |
AC |
1 ms |
384 KB |
subtask1_03.txt |
AC |
1 ms |
512 KB |
subtask1_04.txt |
AC |
3 ms |
2304 KB |
subtask1_05.txt |
AC |
1 ms |
512 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
AC |
2 ms |
896 KB |
subtask1_08.txt |
AC |
1 ms |
256 KB |
subtask1_09.txt |
AC |
2 ms |
1152 KB |
subtask1_10.txt |
AC |
1 ms |
384 KB |
subtask1_11.txt |
AC |
2 ms |
768 KB |
subtask1_12.txt |
AC |
1 ms |
512 KB |
subtask1_13.txt |
AC |
2 ms |
1024 KB |
subtask1_14.txt |
AC |
3 ms |
1920 KB |
subtask1_15.txt |
AC |
4 ms |
4096 KB |
subtask1_16.txt |
AC |
4 ms |
3840 KB |
subtask1_17.txt |
AC |
3 ms |
2048 KB |
subtask1_18.txt |
AC |
2 ms |
896 KB |
subtask1_19.txt |
AC |
1 ms |
384 KB |
subtask1_20.txt |
AC |
1 ms |
384 KB |
subtask1_21.txt |
AC |
3 ms |
2560 KB |
subtask1_22.txt |
AC |
3 ms |
2304 KB |
subtask1_23.txt |
AC |
2 ms |
768 KB |
subtask1_24.txt |
AC |
4 ms |
2944 KB |
subtask1_25.txt |
AC |
5 ms |
4096 KB |
subtask2_01.txt |
AC |
6 ms |
5760 KB |
subtask2_02.txt |
AC |
5 ms |
4736 KB |
subtask2_03.txt |
AC |
21 ms |
23296 KB |
subtask2_04.txt |
AC |
39 ms |
43008 KB |
subtask2_05.txt |
AC |
45 ms |
48128 KB |
subtask2_06.txt |
AC |
38 ms |
40192 KB |
subtask2_07.txt |
AC |
22 ms |
22656 KB |
subtask2_08.txt |
AC |
20 ms |
20864 KB |
subtask2_09.txt |
AC |
74 ms |
81664 KB |
subtask2_10.txt |
AC |
94 ms |
138496 KB |
subtask2_11.txt |
AC |
37 ms |
36608 KB |
subtask2_12.txt |
AC |
129 ms |
146816 KB |
subtask2_13.txt |
AC |
98 ms |
112256 KB |
subtask2_14.txt |
AC |
115 ms |
132864 KB |
subtask2_15.txt |
AC |
8 ms |
8192 KB |
subtask2_16.txt |
AC |
26 ms |
25984 KB |
subtask2_17.txt |
AC |
31 ms |
30464 KB |
subtask2_18.txt |
AC |
91 ms |
99456 KB |
subtask2_19.txt |
AC |
66 ms |
69248 KB |
subtask2_20.txt |
AC |
73 ms |
79872 KB |
subtask2_21.txt |
AC |
65 ms |
70656 KB |
subtask2_22.txt |
AC |
105 ms |
119040 KB |
subtask2_23.txt |
AC |
125 ms |
142464 KB |
subtask2_24.txt |
AC |
120 ms |
179968 KB |
subtask2_25.txt |
AC |
112 ms |
125696 KB |
subtask3_01.txt |
AC |
3 ms |
2560 KB |
subtask3_02.txt |
AC |
47 ms |
52736 KB |
subtask3_03.txt |
AC |
7 ms |
6912 KB |
subtask3_04.txt |
AC |
72 ms |
82432 KB |
subtask3_05.txt |
AC |
119 ms |
181632 KB |
subtask3_06.txt |
AC |
125 ms |
146432 KB |
subtask3_07.txt |
AC |
49 ms |
56320 KB |
subtask3_08.txt |
AC |
81 ms |
85888 KB |
subtask3_09.txt |
AC |
218 ms |
337024 KB |
subtask3_10.txt |
AC |
94 ms |
134784 KB |
subtask3_11.txt |
MLE |
431 ms |
659200 KB |
subtask3_12.txt |
MLE |
421 ms |
645248 KB |
subtask3_13.txt |
MLE |
429 ms |
659200 KB |
subtask3_14.txt |
AC |
186 ms |
212224 KB |
subtask3_15.txt |
AC |
222 ms |
332288 KB |
subtask3_16.txt |
AC |
141 ms |
155392 KB |
subtask3_17.txt |
MLE |
434 ms |
659200 KB |
subtask3_18.txt |
AC |
102 ms |
155264 KB |
subtask3_19.txt |
MLE |
432 ms |
659200 KB |
subtask3_20.txt |
AC |
49 ms |
72064 KB |
subtask3_21.txt |
MLE |
431 ms |
659200 KB |
subtask3_22.txt |
MLE |
432 ms |
659200 KB |
subtask3_23.txt |
MLE |
430 ms |
659200 KB |
subtask3_24.txt |
MLE |
433 ms |
659200 KB |
subtask3_25.txt |
MLE |
429 ms |
659200 KB |