AtCoder Regular Contest 070

Submission #1356393

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],1), ub = k-1;
		bool exist = false;
		
		for (int sum1=0;sum1<=ub;sum1++)
		{
			if (!pre[i-1][sum1]) continue;
			int lb2 = max(lb-sum1,1), 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問題 C - Go Home
User nameユーザ名 Gabriel
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 1313 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
All 0 / 200 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt WA
0_001.txt WA
0_002.txt WA
1_003.txt RE
1_004.txt RE
1_005.txt WA
1_006.txt RE
1_007.txt RE
1_008.txt RE
1_009.txt RE
1_010.txt RE
1_011.txt RE
1_012.txt RE
1_013.txt RE
1_014.txt RE
1_015.txt RE
1_016.txt RE
1_017.txt RE