AtCoder Beginner Contest 008

Submission #1677682

Source codeソースコード

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<map>
#include<cmath>
#include<tuple>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int a = 0;a < i;a++){for(int b = 0;b < j;b++)cerr << v[a][b] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int n;
vector<int> y,x;

map<tuple<int,int,int,int> ,int> memo;

ll solve(int y1,int y2,int x1,int x2)
{
	if(memo.find(make_tuple(y2,y2,x1,x2)) != memo.end())
		return memo[make_tuple(y1,y2,x1,x2)];
	
	
	ll ret = 0;
	
	REP(i,n)
	{
		if(y[i] < y1 || y[i] > y2 || x[i] < x1 || x[i] > x2)
			continue;
		
		ll tmp = y2 - y1 + x2 - x1 + 1;
		tmp += solve(y1,y[i] - 1,x1,x[i] - 1);
		tmp += solve(y[i] + 1,y2,x[i] + 1,x2);
		tmp += solve(y1,y[i] - 1,x[i] + 1,x2);
		tmp += solve(y[i] + 1,y2,x1,x[i] - 1);
		
		ret = max(ret,tmp);
		
	}
	
	return memo[make_tuple(y1,y2,x1,x2)] = ret;
}

int main()
{
	int w,h;
	cin >> w >> h >> n;
	x.resize(n);
	y.resize(n);
	REP(i,n)
	{
		cin >> x[i] >> y[i];
	}
	
	cout << solve(1,h,1,w) << endl;
	
	return 0;
}

Submission

Task問題 D - 金塊ゲーム
User nameユーザ名 seica
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1732 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 0 / 80 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 0 / 19 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 0 / 1 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 2 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 2 ms 256 KB
subtask1_04.txt WA
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 256 KB
subtask1_09.txt AC 1 ms 256 KB
subtask1_10.txt AC 1 ms 256 KB
subtask1_11.txt AC 1 ms 256 KB
subtask1_12.txt AC 1 ms 256 KB
subtask1_13.txt AC 1 ms 256 KB
subtask1_14.txt AC 1 ms 256 KB
subtask1_15.txt WA
subtask1_16.txt WA
subtask1_17.txt AC 2 ms 256 KB
subtask1_18.txt AC 2 ms 256 KB
subtask1_19.txt WA
subtask1_20.txt AC 2 ms 256 KB
subtask1_21.txt AC 2 ms 256 KB
subtask1_22.txt AC 2 ms 256 KB
subtask1_23.txt AC 2 ms 256 KB
subtask1_24.txt AC 2 ms 256 KB
subtask1_25.txt AC 2 ms 256 KB
subtask2_01.txt WA
subtask2_02.txt AC 12 ms 384 KB
subtask2_03.txt WA
subtask2_04.txt AC 53 ms 512 KB
subtask2_05.txt AC 815 ms 512 KB
subtask2_06.txt AC 562 ms 640 KB
subtask2_07.txt AC 679 ms 640 KB
subtask2_08.txt WA
subtask2_09.txt WA
subtask2_10.txt WA
subtask2_11.txt AC 1260 ms 896 KB
subtask2_12.txt TLE
subtask2_13.txt WA
subtask2_14.txt WA
subtask2_15.txt AC 2 ms 256 KB
subtask2_16.txt WA
subtask2_17.txt WA
subtask2_18.txt AC 2648 ms 896 KB
subtask2_19.txt AC 1005 ms 768 KB
subtask2_20.txt WA
subtask2_21.txt WA
subtask2_22.txt WA
subtask2_23.txt TLE
subtask2_24.txt AC 1484 ms 896 KB
subtask2_25.txt TLE
subtask3_01.txt AC 2 ms 256 KB
subtask3_02.txt AC 31 ms 384 KB
subtask3_03.txt AC 10 ms 384 KB
subtask3_04.txt AC 28 ms 384 KB
subtask3_05.txt AC 177 ms 512 KB
subtask3_06.txt AC 191 ms 512 KB
subtask3_07.txt AC 74 ms 512 KB
subtask3_08.txt AC 422 ms 640 KB
subtask3_09.txt AC 1532 ms 640 KB
subtask3_10.txt TLE
subtask3_11.txt AC 1590 ms 896 KB
subtask3_12.txt TLE
subtask3_13.txt TLE
subtask3_14.txt AC 2101 ms 896 KB
subtask3_15.txt AC 3360 ms 896 KB
subtask3_16.txt AC 1195 ms 896 KB
subtask3_17.txt TLE
subtask3_18.txt AC 184 ms 512 KB
subtask3_19.txt AC 1896 ms 896 KB
subtask3_20.txt AC 622 ms 640 KB
subtask3_21.txt TLE
subtask3_22.txt TLE
subtask3_23.txt TLE
subtask3_24.txt TLE
subtask3_25.txt AC 1484 ms 896 KB