Submission #163678


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#define MX 155
#define SIZE 300005

using namespace std;

bool dp[2][SIZE];
int cnt[MX];
int in[SIZE];

int main()
{
	int q,m,n;
	scanf("%d %d %d",&q,&m,&n);
	int all=0;
	for(int i=0;i<m;i++)
	{
		int ax;
		scanf("%d",&ax);
		all+=ax;
		cnt[ax]++;
	}
	int pos=0;
	memset(dp[pos],false,sizeof(dp[pos]));
	dp[pos][0]=true;
	for(int i=1;i<MX;i++)
	{
		pos^=1;
		memset(dp[pos],false,sizeof(dp[pos]));
		for(int j=0;j<i;j++)
		{
			int sum=0;
			for(int k=j;k<=all;k+=i)
			{
				sum+=dp[pos^1][k];
				if(k-(cnt[i]+1)*i>=0) sum-=dp[pos^1][k-(cnt[i]+1)*i];
				dp[pos][k]=sum;
			}
		}
	}
	if(dp[pos][q])
	{
		printf("%d\n",q);
		return 0;
	}
	int mx=0;
	for(int i=0;i<=all;i++)
	{
		if(dp[pos][i])
		{
			mx=i;
		}
	}
	if(mx>q)
	{
		printf("%d\n",q-1);
		return 0;
	}
	for(int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		in[i]=a;
	}
	sort(in,in+n);
	int now=0;
	for(int i=n-1;i>=0;i--)
	{
		if(mx<q)
		{
			mx+=in[i];
			now++;
		}
	}
	printf("%d\n",q-now);
	return 0;
}

Submission Info

Submission Time
Task 14 - Farmer
User yutaka1999
Language C++ (G++ 4.6.4)
Score 100
Code Size 1126 Byte
Status AC
Exec Time 130 ms
Memory 1428 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:17:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:22:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:65:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Set01 Set02 Set03 Set04 Set05 Set06 Set07 Set08 Set09 Set10 Set11 Set12 Set13 Set14 Set15 Set16 Set17 Set18 Set19 Set20
Score / Max Score 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
Set01 01
Set02 02
Set03 03
Set04 04
Set05 05
Set06 06
Set07 07
Set08 08
Set09 09
Set10 10
Set11 11
Set12 12
Set13 13
Set14 14
Set15 15
Set16 16
Set17 17
Set18 18
Set19 19
Set20 20
Case Name Status Exec Time Memory
01 AC 23 ms 1424 KB
02 AC 25 ms 1308 KB
03 AC 25 ms 1312 KB
04 AC 25 ms 1196 KB
05 AC 25 ms 1308 KB
06 AC 25 ms 1312 KB
07 AC 26 ms 1308 KB
08 AC 25 ms 1312 KB
09 AC 24 ms 1312 KB
10 AC 28 ms 1304 KB
11 AC 70 ms 1312 KB
12 AC 72 ms 1308 KB
13 AC 71 ms 1304 KB
14 AC 71 ms 1296 KB
15 AC 76 ms 1104 KB
16 AC 91 ms 1200 KB
17 AC 87 ms 1304 KB
18 AC 87 ms 1428 KB
19 AC 87 ms 1300 KB
20 AC 130 ms 1304 KB