Contest Duration: ~ (local time) (120 minutes) Back to Home

Submission #4073952

Source Code Expand

Copy
```#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
for(auto v : V){
cout << v << " ";
}
cout << endl;
}

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

const ll mod = 1e9 + 7;
const ll inf = 1e18;

struct Point{
ll x;
ll y;
Point(ll x, ll y): x(x), y(y) {}
Point(){}

bool operator<(const Point &another) const
{
if(x==another.x){
return y < another.y;
}
return x < another.x;
}
};

// M exist map
map<Point, bool> mp;

const int L_MAX = 82;
ll dp[L_MAX][L_MAX][L_MAX][L_MAX] = {};

ll calc(int sx, int sy, int gx, int gy){
ll localW = gx - sx + 1;
ll localH = gy - sy + 1;

if(dp[sx][sy][gx][gy]!=-1){
return dp[sx][sy][gx][gy];
}

if(gx < sx || gy < sy){
dp[sx][sy][gx][gy] = 0;
return 0;
}

// 1コマ
if(sx==gx && sy == gy){
if(mp[Point(sx, sy)]){
dp[sx][sy][gx][gy] = 1;
return 1;
}else{
dp[sx][sy][gx][gy] = 0;
return 0;
}
}

FOR(x, sx, gx+1){
FOR(y, sy, gy+1){
if(mp[Point(x,y)]){
ll gold = (localW + localH - 1)
+ calc(sx, sy, x-1, y-1) // 左下
+ calc(sx, y+1, x-1, gy) // 左上
+ calc(x+1, sy, gx, y-1) // 右下
+ calc(x+1, y+1, gx, gy); // 右上
if(gold > dp[sx][sy][gx][gy]){
dp[sx][sy][gx][gy] = gold;
}
}
}
}
if(dp[sx][sy][gx][gy]==-1){
return dp[sx][sy][gx][gy] = 0;
}else{
return dp[sx][sy][gx][gy];
}
}

int main(){
cin.tie(0);
ios::sync_with_stdio(false);

// input
ll W, H;
cin >> W >> H;

if(W > 80 || H > 80){
p(0);
return 0;
}

ll N;
cin >> N;

// マシン登録
FOR(i, 0, N){
ll x, y;
cin >> x >> y;
mp[Point(x, y)] = true;
}

FOR(i, 0, L_MAX){
FOR(j, 0, L_MAX){
FOR(k, 0, L_MAX){
FOR(l, 0, L_MAX){
dp[i][j][k][l] = -1;
}
}
}
}

p(calc(1, 1, W, H));

return 0;
}```

#### Submission Info

Submission Time 2019-01-23 19:36:13+0900 D - 金塊ゲーム peroon C++14 (GCC 5.4.1) 99 2769 Byte WA 425 ms 354044 KB

#### Judge Result

Score / Max Score 0 / 0 80 / 80 19 / 19 0 / 1
Status
 AC × 3
 AC × 25
 AC × 50
 AC × 50 WA × 25
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt 133 ms 354044 KB
sample_02.txt 126 ms 353536 KB
sample_03.txt 126 ms 353536 KB
subtask1_01.txt 126 ms 353536 KB
subtask1_02.txt 126 ms 353536 KB
subtask1_03.txt 126 ms 353536 KB
subtask1_04.txt 127 ms 353536 KB
subtask1_05.txt 127 ms 353536 KB
subtask1_06.txt 126 ms 353536 KB
subtask1_07.txt 126 ms 353536 KB
subtask1_08.txt 126 ms 353536 KB
subtask1_09.txt 132 ms 353920 KB
subtask1_10.txt 128 ms 353920 KB
subtask1_11.txt 129 ms 353920 KB
subtask1_12.txt 126 ms 353536 KB
subtask1_13.txt 126 ms 353536 KB
subtask1_14.txt 135 ms 353920 KB
subtask1_15.txt 137 ms 353920 KB
subtask1_16.txt 127 ms 353536 KB
subtask1_17.txt 127 ms 353536 KB
subtask1_18.txt 126 ms 353536 KB
subtask1_19.txt 126 ms 353536 KB
subtask1_20.txt 126 ms 353536 KB
subtask1_21.txt 128 ms 353536 KB
subtask1_22.txt 129 ms 353664 KB
subtask1_23.txt 128 ms 353536 KB
subtask1_24.txt 136 ms 353792 KB
subtask1_25.txt 142 ms 353920 KB
subtask2_01.txt 129 ms 353536 KB
subtask2_02.txt 128 ms 353536 KB
subtask2_03.txt 149 ms 353536 KB
subtask2_04.txt 231 ms 353920 KB
subtask2_05.txt 213 ms 353792 KB
subtask2_06.txt 192 ms 353664 KB
subtask2_07.txt 153 ms 353536 KB
subtask2_08.txt 150 ms 353536 KB
subtask2_09.txt 281 ms 353664 KB
subtask2_10.txt 406 ms 353920 KB
subtask2_11.txt 192 ms 353536 KB
subtask2_12.txt 376 ms 353920 KB
subtask2_13.txt 307 ms 353920 KB
subtask2_14.txt 313 ms 353920 KB
subtask2_15.txt 147 ms 353920 KB
subtask2_16.txt 162 ms 353536 KB
subtask2_17.txt 177 ms 353536 KB
subtask2_18.txt 307 ms 353792 KB
subtask2_19.txt 261 ms 353664 KB
subtask2_20.txt 297 ms 353664 KB
subtask2_21.txt 280 ms 353664 KB
subtask2_22.txt 333 ms 353792 KB
subtask2_23.txt 315 ms 353792 KB
subtask2_24.txt 413 ms 353920 KB
subtask2_25.txt 425 ms 353920 KB
subtask3_01.txt 1 ms 256 KB
subtask3_02.txt 1 ms 256 KB
subtask3_03.txt 1 ms 256 KB
subtask3_04.txt 1 ms 256 KB
subtask3_05.txt 1 ms 256 KB
subtask3_06.txt 1 ms 256 KB
subtask3_07.txt 1 ms 256 KB
subtask3_08.txt 1 ms 256 KB
subtask3_09.txt 1 ms 256 KB
subtask3_10.txt 1 ms 256 KB
subtask3_11.txt 1 ms 256 KB
subtask3_12.txt 1 ms 256 KB
subtask3_13.txt 1 ms 256 KB
subtask3_14.txt 1 ms 256 KB
subtask3_15.txt 1 ms 256 KB
subtask3_16.txt 1 ms 256 KB
subtask3_17.txt 1 ms 256 KB
subtask3_18.txt 1 ms 256 KB
subtask3_19.txt 1 ms 256 KB
subtask3_20.txt 1 ms 256 KB
subtask3_21.txt 1 ms 256 KB
subtask3_22.txt 1 ms 256 KB
subtask3_23.txt 1 ms 256 KB
subtask3_24.txt 1 ms 256 KB
subtask3_25.txt 1 ms 256 KB