AtCoder Regular Contest 070

Submission #1356405

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);
	ll sum = 0;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]), sum += (ll)a[i];
	if (sum < k)
	{
		printf("%d\n",n);
		return 0;
	}
	
	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状態 WA
Score得点 0
Source lengthソースコード長 1312 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

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:28:59: 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]), sum += (ll)a[i];
^

Test case

Set

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