#408145 (C++17) No.973 余興

提出ソース

結果

問題	No.973 余興
ユーザー	沙耶花
提出日時	2019-12-13 07:43:14
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	340 ms / 4,000 ms
コード長	1,350 bytes
コンパイル時間	2,541 ms
コンパイル使用メモリ	202,912 KB
実行使用メモリ	198,960 KB
最終ジャッジ日時	2024-12-17 22:08:48
合計ジャッジ時間	14,739 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	319 ms 198,824 KB
testcase_01	AC	339 ms 198,872 KB
testcase_02	AC	333 ms 198,832 KB
testcase_03	AC	339 ms 198,892 KB
testcase_04	AC	331 ms 198,960 KB
testcase_05	AC	340 ms 198,864 KB
testcase_06	AC	325 ms 197,272 KB
testcase_07	AC	340 ms 197,196 KB
testcase_08	AC	321 ms 197,088 KB
testcase_09	AC	331 ms 197,328 KB
testcase_10	AC	306 ms 196,924 KB
testcase_11	AC	114 ms 124,544 KB
testcase_12	AC	117 ms 123,416 KB
testcase_13	AC	118 ms 124,420 KB
testcase_14	AC	124 ms 121,188 KB
testcase_15	AC	18 ms 44,824 KB
testcase_16	AC	19 ms 44,824 KB
testcase_17	AC	13 ms 34,612 KB
testcase_18	AC	16 ms 40,668 KB
testcase_19	AC	16 ms 40,700 KB
testcase_20	AC	14 ms 36,472 KB
testcase_21	AC	20 ms 45,076 KB
testcase_22	AC	18 ms 44,804 KB
testcase_23	AC	16 ms 41,028 KB
testcase_24	AC	16 ms 40,844 KB
testcase_25	AC	10 ms 28,524 KB
testcase_26	AC	14 ms 34,476 KB
testcase_27	AC	22 ms 46,892 KB
testcase_28	AC	16 ms 38,888 KB
testcase_29	AC	16 ms 38,900 KB
testcase_30	AC	316 ms 198,860 KB
testcase_31	AC	332 ms 198,960 KB
testcase_32	AC	333 ms 198,816 KB
testcase_33	AC	329 ms 197,284 KB
testcase_34	AC	332 ms 198,608 KB
testcase_35	AC	316 ms 198,880 KB
testcase_36	AC	315 ms 197,568 KB
testcase_37	AC	305 ms 197,676 KB
testcase_38	AC	337 ms 198,676 KB
testcase_39	AC	318 ms 197,148 KB
testcase_40	AC	2 ms 6,816 KB
testcase_41	AC	2 ms 6,816 KB
testcase_42	AC	2 ms 6,820 KB
testcase_43	AC	2 ms 6,820 KB
testcase_44	AC	2 ms 6,820 KB
testcase_45	AC	3 ms 9,904 KB
testcase_46	AC	316 ms 198,888 KB
testcase_47	AC	324 ms 197,416 KB
testcase_48	AC	330 ms 198,868 KB
testcase_49	AC	273 ms 194,228 KB
testcase_50	AC	325 ms 197,040 KB
testcase_51	AC	318 ms 198,840 KB
testcase_52	AC	324 ms 197,292 KB
testcase_53	AC	316 ms 198,216 KB
testcase_54	AC	333 ms 197,408 KB
testcase_55	AC	336 ms 198,828 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000000000000



int main(){
	
	int N,X;
	cin>>N>>X;
	
	vector<int> a(N);
	for(int i=0;i<N;i++){
		cin>>a[i];
	}
	
	vector<int> left(N),right(N);
	
	int l = 0;
	int r = 0;
	int sum = 0;
	
	while(true){
		while(r != N && sum + a[r] <= X){
			sum += a[r];
			r++;
		}
		left[l] = r-l;
		sum -= a[l];
		l++;
		if(l==N)break;
	}
	
	l=N-1;
	r=N-1;
	sum=0;
	
	while(true){
		while(l!=-1&&sum+a[l]<=X){
			sum += a[l];
			l--;
		}
		right[r] = r-l;
		sum -= a[r];
		r--;
		if(r<0)break;
	}
	
	
	//vector<vector<int>> dp_l(N,vector<int>(N+1)),dp_r(N,vector<int>(N+1));
	int dp_l[5000][5001],dp_r[5000][5001];
	
	for(int i=0;i<N;i++){
		dp_l[i][0]=0;
		dp_r[i][0]=0;
	}
	
	int cnt,x;
	
	for(int i=1;i<=N;i++){
		for(int j=0;j<N-i+1;j++){
			l = j;
			r = j+i-1;
			
			dp_l[l][i]=dp_l[l][i-1];
			dp_r[r][i]=dp_r[r][i-1];
			
			cnt = min(left[l],i-1);
			x = dp_r[r][i-1]-dp_r[r][i-cnt-1];
			if(x!=cnt){
				dp_l[l][i]++;
				dp_r[r][i]++;
				continue;
			}
			
			cnt = min(right[r],i-1);
			x = dp_l[l][i-1]-dp_l[l][i-cnt-1];
			if(x!=cnt){
				dp_l[l][i]++;
				dp_r[r][i]++;
				continue;
			}
			
		}
	}

	
	if(dp_l[0][N]==dp_l[0][N-1]){
		cout<<"B"<<endl;
	}
	else{
		cout<<"A"<<endl;
	}
	
	


	return 0;
}

yukicoder

結果

テストケース

ソースコード