AtCoder Regular Contest 043

Submission #470543

Source codeソースコード

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <utility>
using namespace std;

int n, d[100000];
const int mod=1000000007;

int dp[100001][4];

int rec(int x, int y){ //問題xをy問目に選ぶ
	if(dp[x][y]>=0){
		//printf("!!ret!!\n");	
		return dp[x][y];
	}
	int ret=0;

	if(y==3){ //最後に到達した
		ret=1;
	}
	else{
		int times;
		if(y==0) times=4;
		else if(y==1) times=2;
		else if(y==2) times=1;
		
		for(int i=x+1; i<=n-3+y; ++i){
			if(d[i]*times > d[n-1]) break;
			
			if(d[x]*2<=d[i]){ //次の問題の候補になり得る
				ret += rec(i, y+1);
				ret%=mod;
			}
		}
	}
	
	//printf("(x,y)=(%d,%d), ret=%d\n", x, y, ret);
	return dp[x][y]=ret;
}


int main(){
	memset(dp, -1, sizeof(dp));
	
	//input
	scanf(" %d", &n);
	for(int i=0; i<n; ++i) scanf(" %d", &d[i]);
	
	sort(d, d+n);
	
	int ans=0;
	for(int i=0; i<=n-4; ++i){
		if(d[i]*8<=d[n-1]){
			ans+=rec(i,0);
			ans%=mod;
		}
	}
	
	printf("%d\n", ans);	
}

Submission

Task問題 B - 難易度
User nameユーザ名 imulan
Created time投稿日時
Language言語 C++ (GCC 4.9.2)
Status状態 TLE
Score得点 50
Source lengthソースコード長 1054 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d", &n);
^
./Main.cpp:50:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<n; ++i) scanf(" %d", &d[i]);
^

Test case

Set

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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 29 ms 2456 KB
sample_02.txt AC 31 ms 2280 KB
sample_03.txt AC 31 ms 2344 KB
subtask1_01.txt AC 29 ms 2336 KB
subtask1_02.txt AC 29 ms 2344 KB
subtask1_03.txt AC 59 ms 2344 KB
subtask1_04.txt AC 48 ms 2340 KB
subtask1_05.txt AC 44 ms 2336 KB
subtask1_06.txt AC 67 ms 2332 KB
subtask1_07.txt AC 43 ms 2328 KB
subtask1_08.txt AC 58 ms 2452 KB
subtask1_09.txt AC 61 ms 2460 KB
subtask1_10.txt AC 35 ms 2332 KB
subtask1_11.txt AC 53 ms 2336 KB
subtask1_12.txt AC 61 ms 2452 KB
subtask1_13.txt AC 37 ms 2340 KB
subtask1_14.txt AC 45 ms 2456 KB
subtask1_15.txt AC 71 ms 2268 KB
subtask1_16.txt AC 67 ms 2328 KB
subtask1_17.txt AC 71 ms 2268 KB
subtask1_18.txt AC 70 ms 2336 KB
subtask1_19.txt AC 68 ms 2456 KB
subtask2_01.txt TLE
subtask2_02.txt TLE
subtask2_03.txt AC 692 ms 2336 KB
subtask2_04.txt AC 899 ms 2328 KB
subtask2_05.txt TLE
subtask2_06.txt TLE
subtask2_07.txt AC 105 ms 2452 KB
subtask2_08.txt AC 108 ms 2452 KB
subtask2_09.txt TLE
subtask2_10.txt TLE
subtask2_11.txt AC 150 ms 2344 KB
subtask2_12.txt TLE
subtask2_13.txt AC 261 ms 2340 KB
subtask2_14.txt TLE
subtask2_15.txt TLE
subtask2_16.txt TLE
subtask2_17.txt TLE
subtask2_18.txt TLE
subtask2_19.txt TLE
subtask2_20.txt TLE
subtask2_21.txt TLE