Submission #1584967
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, 0, 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<int>>>> m2(w, vector<vector<vector<int>>>(h, vector<vector<int>>(w+1, vector<int>(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 |
100 |
Code Size |
3169 Byte |
Status |
AC |
Exec Time |
105 ms |
Memory |
88704 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
80 / 80 |
19 / 19 |
1 / 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 |
640 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
384 KB |
subtask1_04.txt |
AC |
2 ms |
1024 KB |
subtask1_05.txt |
AC |
1 ms |
384 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
AC |
1 ms |
512 KB |
subtask1_08.txt |
AC |
1 ms |
256 KB |
subtask1_09.txt |
AC |
2 ms |
512 KB |
subtask1_10.txt |
AC |
1 ms |
256 KB |
subtask1_11.txt |
AC |
1 ms |
384 KB |
subtask1_12.txt |
AC |
1 ms |
384 KB |
subtask1_13.txt |
AC |
2 ms |
640 KB |
subtask1_14.txt |
AC |
2 ms |
640 KB |
subtask1_15.txt |
AC |
2 ms |
1280 KB |
subtask1_16.txt |
AC |
2 ms |
1408 KB |
subtask1_17.txt |
AC |
2 ms |
896 KB |
subtask1_18.txt |
AC |
2 ms |
512 KB |
subtask1_19.txt |
AC |
1 ms |
384 KB |
subtask1_20.txt |
AC |
1 ms |
384 KB |
subtask1_21.txt |
AC |
2 ms |
1024 KB |
subtask1_22.txt |
AC |
2 ms |
1024 KB |
subtask1_23.txt |
AC |
2 ms |
512 KB |
subtask1_24.txt |
AC |
2 ms |
1024 KB |
subtask1_25.txt |
AC |
2 ms |
1280 KB |
subtask2_01.txt |
AC |
5 ms |
3328 KB |
subtask2_02.txt |
AC |
3 ms |
2176 KB |
subtask2_03.txt |
AC |
11 ms |
8704 KB |
subtask2_04.txt |
AC |
15 ms |
12288 KB |
subtask2_05.txt |
AC |
18 ms |
14720 KB |
subtask2_06.txt |
AC |
21 ms |
16384 KB |
subtask2_07.txt |
AC |
16 ms |
11904 KB |
subtask2_08.txt |
AC |
16 ms |
11648 KB |
subtask2_09.txt |
AC |
37 ms |
29184 KB |
subtask2_10.txt |
AC |
53 ms |
41728 KB |
subtask2_11.txt |
AC |
25 ms |
18944 KB |
subtask2_12.txt |
AC |
52 ms |
40960 KB |
subtask2_13.txt |
AC |
32 ms |
27008 KB |
subtask2_14.txt |
AC |
39 ms |
32512 KB |
subtask2_15.txt |
AC |
3 ms |
2048 KB |
subtask2_16.txt |
AC |
17 ms |
12928 KB |
subtask2_17.txt |
AC |
21 ms |
15232 KB |
subtask2_18.txt |
AC |
43 ms |
33024 KB |
subtask2_19.txt |
AC |
35 ms |
27904 KB |
subtask2_20.txt |
AC |
40 ms |
30464 KB |
subtask2_21.txt |
AC |
31 ms |
24320 KB |
subtask2_22.txt |
AC |
46 ms |
35200 KB |
subtask2_23.txt |
AC |
56 ms |
45056 KB |
subtask2_24.txt |
AC |
59 ms |
46848 KB |
subtask2_25.txt |
AC |
45 ms |
34432 KB |
subtask3_01.txt |
AC |
2 ms |
768 KB |
subtask3_02.txt |
AC |
10 ms |
8448 KB |
subtask3_03.txt |
AC |
4 ms |
2432 KB |
subtask3_04.txt |
AC |
17 ms |
13696 KB |
subtask3_05.txt |
AC |
35 ms |
29184 KB |
subtask3_06.txt |
AC |
26 ms |
22144 KB |
subtask3_07.txt |
AC |
17 ms |
13952 KB |
subtask3_08.txt |
AC |
27 ms |
22016 KB |
subtask3_09.txt |
AC |
56 ms |
45952 KB |
subtask3_10.txt |
AC |
48 ms |
37760 KB |
subtask3_11.txt |
AC |
103 ms |
88704 KB |
subtask3_12.txt |
AC |
104 ms |
88704 KB |
subtask3_13.txt |
AC |
104 ms |
88704 KB |
subtask3_14.txt |
AC |
63 ms |
49408 KB |
subtask3_15.txt |
AC |
73 ms |
60544 KB |
subtask3_16.txt |
AC |
53 ms |
41344 KB |
subtask3_17.txt |
AC |
105 ms |
88704 KB |
subtask3_18.txt |
AC |
36 ms |
29056 KB |
subtask3_19.txt |
AC |
104 ms |
88704 KB |
subtask3_20.txt |
AC |
22 ms |
17920 KB |
subtask3_21.txt |
AC |
105 ms |
88704 KB |
subtask3_22.txt |
AC |
104 ms |
88704 KB |
subtask3_23.txt |
AC |
104 ms |
88704 KB |
subtask3_24.txt |
AC |
104 ms |
88704 KB |
subtask3_25.txt |
AC |
104 ms |
88704 KB |