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
Task D - 金塊ゲーム
User peroon
Language C++14 (GCC 5.4.1)
Score 99
Code Size 2769 Byte
Status
Exec Time 425 ms
Memory 354044 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 80 / 80 19 / 19 0 / 1
Status
× 3
× 25
× 50
× 50
× 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 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