AtCoder Beginner Contest 008

Submission #1677704

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(y1,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状態 AC
Score得点 100
Source lengthソースコード長 1732 Byte
File nameファイル名
Exec time実行時間 23 ms
Memory usageメモリ使用量 896 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 80 / 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 19 / 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 1 / 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 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
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 AC 1 ms 256 KB
subtask1_16.txt AC 1 ms 256 KB
subtask1_17.txt AC 1 ms 256 KB
subtask1_18.txt AC 1 ms 256 KB
subtask1_19.txt AC 1 ms 256 KB
subtask1_20.txt AC 1 ms 256 KB
subtask1_21.txt AC 1 ms 256 KB
subtask1_22.txt AC 1 ms 256 KB
subtask1_23.txt AC 1 ms 256 KB
subtask1_24.txt AC 1 ms 256 KB
subtask1_25.txt AC 1 ms 256 KB
subtask2_01.txt AC 3 ms 384 KB
subtask2_02.txt AC 3 ms 384 KB
subtask2_03.txt AC 5 ms 512 KB
subtask2_04.txt AC 5 ms 512 KB
subtask2_05.txt AC 8 ms 512 KB
subtask2_06.txt AC 11 ms 640 KB
subtask2_07.txt AC 11 ms 640 KB
subtask2_08.txt AC 11 ms 640 KB
subtask2_09.txt AC 21 ms 896 KB
subtask2_10.txt AC 20 ms 896 KB
subtask2_11.txt AC 21 ms 896 KB
subtask2_12.txt AC 22 ms 896 KB
subtask2_13.txt AC 11 ms 640 KB
subtask2_14.txt AC 10 ms 640 KB
subtask2_15.txt AC 1 ms 256 KB
subtask2_16.txt AC 11 ms 640 KB
subtask2_17.txt AC 22 ms 896 KB
subtask2_18.txt AC 23 ms 896 KB
subtask2_19.txt AC 21 ms 896 KB
subtask2_20.txt AC 21 ms 896 KB
subtask2_21.txt AC 21 ms 896 KB
subtask2_22.txt AC 21 ms 896 KB
subtask2_23.txt AC 21 ms 896 KB
subtask2_24.txt AC 21 ms 896 KB
subtask2_25.txt AC 23 ms 896 KB
subtask3_01.txt AC 1 ms 256 KB
subtask3_02.txt AC 3 ms 384 KB
subtask3_03.txt AC 2 ms 384 KB
subtask3_04.txt AC 4 ms 384 KB
subtask3_05.txt AC 7 ms 512 KB
subtask3_06.txt AC 5 ms 512 KB
subtask3_07.txt AC 5 ms 512 KB
subtask3_08.txt AC 11 ms 640 KB
subtask3_09.txt AC 12 ms 640 KB
subtask3_10.txt AC 23 ms 896 KB
subtask3_11.txt AC 20 ms 896 KB
subtask3_12.txt AC 23 ms 896 KB
subtask3_13.txt AC 22 ms 896 KB
subtask3_14.txt AC 21 ms 896 KB
subtask3_15.txt AC 21 ms 896 KB
subtask3_16.txt AC 21 ms 896 KB
subtask3_17.txt AC 21 ms 896 KB
subtask3_18.txt AC 8 ms 512 KB
subtask3_19.txt AC 20 ms 896 KB
subtask3_20.txt AC 11 ms 640 KB
subtask3_21.txt AC 22 ms 896 KB
subtask3_22.txt AC 22 ms 896 KB
subtask3_23.txt AC 21 ms 896 KB
subtask3_24.txt AC 21 ms 896 KB
subtask3_25.txt AC 20 ms 896 KB