AtCoder Regular Contest 070

Submission #1356416

Source codeソースコード

#include <iostream>
#include <cstring>
#include <bitset>
#include <cstdio>
using namespace std;
typedef long long ll;

const int maxn = 5010;

bitset<maxn> pre[maxn],suf[maxn],tmp;
int a[maxn];
int sum[maxn];

bool check(int x, int lb, int ub)
{
	for (int i=lb;i<=ub;i++)
		if (suf[x][i]) return true;
	return false;
}
	
int main()
{
	//freopen("D.in","r",stdin);
	//freopen("D.out","w",stdout);
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	pre[0].reset(); 
	pre[0][0] = 1;
	for (int i=1;i<=n;i++)
	{
		tmp.reset();
		if (a[i] < maxn) tmp = pre[i-1] << a[i];
		pre[i] = pre[i-1] | tmp;
	}
	
	suf[n+1].reset();
	suf[n+1][0] = 1;
	for (int i=n;i>=1;i--)
	{
		tmp.reset();
		if (a[i] < maxn) tmp = suf[i+1] << a[i];
		suf[i] = suf[i+1] | tmp;
	}
	
	int cnt = 0;
	for (int i=1;i<=n;i++)
	{
		int lb = max(k-a[i],0), ub = k-1;
		bool exist = false;
		for (int sum1=0;sum1<=ub;sum1++)
		{
			if (!pre[i-1][sum1]) continue;
			int lb2 = max(lb-sum1,0), ub2 = ub-sum1;
			if (ub2 < lb2) continue;
			if (check(i+1,lb2,ub2)) 
			{
				exist = true;
				break;
			}
		}
		if (!exist) cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

Submission

Task問題 D - No Need
User nameユーザ名 Gabriel
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 600
Source lengthソースコード長 1218 Byte
File nameファイル名
Exec time実行時間 56 ms
Memory usageメモリ使用量 6400 KB

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

./Main.cpp: In function ‘int main()’:
./Main.cpp:26:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
^
./Main.cpp:27:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt
Subtask 300 / 300 0_000.txt,0_001.txt,0_002.txt,1_003.txt,1_004.txt,1_005.txt,1_006.txt,1_007.txt,1_008.txt,1_009.txt,1_010.txt,1_011.txt,1_012.txt,1_013.txt,1_014.txt,1_015.txt,1_016.txt,1_017.txt,1_018.txt,1_019.txt,1_020.txt,1_021.txt,1_022.txt,1_023.txt,1_024.txt,1_025.txt
All 300 / 300 0_000.txt,0_001.txt,0_002.txt,1_003.txt,1_004.txt,1_005.txt,1_006.txt,1_007.txt,1_008.txt,1_009.txt,1_010.txt,1_011.txt,1_012.txt,1_013.txt,1_014.txt,1_015.txt,1_016.txt,1_017.txt,1_018.txt,1_019.txt,1_020.txt,1_021.txt,1_022.txt,1_023.txt,1_024.txt,1_025.txt,2_026.txt,2_027.txt,2_028.txt,2_029.txt,2_030.txt,2_031.txt,2_032.txt,2_033.txt,2_034.txt,2_035.txt,2_036.txt,2_037.txt,2_038.txt,2_039.txt,2_040.txt,2_041.txt,2_042.txt,2_043.txt,2_044.txt,2_045.txt,2_046.txt,2_047.txt,2_048.txt,2_049.txt,2_050.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 2 ms 2304 KB
0_001.txt AC 2 ms 2304 KB
0_002.txt AC 2 ms 2304 KB
1_003.txt AC 2 ms 2304 KB
1_004.txt AC 2 ms 2304 KB
1_005.txt AC 2 ms 2304 KB
1_006.txt AC 2 ms 2304 KB
1_007.txt AC 2 ms 2304 KB
1_008.txt AC 2 ms 2560 KB
1_009.txt AC 2 ms 2560 KB
1_010.txt AC 2 ms 2560 KB
1_011.txt AC 2 ms 2560 KB
1_012.txt AC 2 ms 2560 KB
1_013.txt AC 2 ms 2560 KB
1_014.txt AC 2 ms 2560 KB
1_015.txt AC 2 ms 2560 KB
1_016.txt AC 2 ms 2304 KB
1_017.txt AC 2 ms 2304 KB
1_018.txt AC 2 ms 2304 KB
1_019.txt AC 2 ms 2560 KB
1_020.txt AC 2 ms 2560 KB
1_021.txt AC 2 ms 2560 KB
1_022.txt AC 2 ms 2432 KB
1_023.txt AC 2 ms 2432 KB
1_024.txt AC 2 ms 2560 KB
1_025.txt AC 2 ms 2560 KB
2_026.txt AC 2 ms 2304 KB
2_027.txt AC 2 ms 2304 KB
2_028.txt AC 2 ms 2304 KB
2_029.txt AC 40 ms 6400 KB
2_030.txt AC 56 ms 6400 KB
2_031.txt AC 5 ms 6400 KB
2_032.txt AC 5 ms 6400 KB
2_033.txt AC 6 ms 6400 KB
2_034.txt AC 6 ms 6400 KB
2_035.txt AC 7 ms 6400 KB
2_036.txt AC 8 ms 6400 KB
2_037.txt AC 2 ms 2304 KB
2_038.txt AC 2 ms 2304 KB
2_039.txt AC 2 ms 2304 KB
2_040.txt AC 9 ms 6400 KB
2_041.txt AC 9 ms 6400 KB
2_042.txt AC 8 ms 6400 KB
2_043.txt AC 8 ms 6272 KB
2_044.txt AC 8 ms 6400 KB
2_045.txt AC 7 ms 6400 KB
2_046.txt AC 19 ms 6400 KB
2_047.txt AC 28 ms 6400 KB
2_048.txt AC 36 ms 6400 KB
2_049.txt AC 34 ms 6400 KB
2_050.txt AC 32 ms 6400 KB