QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404598#2544. Flatland CurrencyZxc200611WA 0ms10040kbC++141.2kb2024-05-04 10:17:312024-05-04 10:17:32

Judging History

你现在查看的是最新测评结果

  • [2024-05-04 10:17:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:10040kb
  • [2024-05-04 10:17:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x1f1f1f1f1f1f1f1f;
int n,c,c1,c5;
int f[2][410000];
vector<int> v[5];
signed main()
{
	cin>>n>>c;
	c5=c/5,c1=c%5;
	for(int i=0;i<=4;i++)
		v[i]=vector<int>({0});
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		int x5=(x+4)/5,x1=((-x)%5+5)%5;
		v[x1].push_back(x5);
	}
	for(int i=0;i<=4;i++)
		partial_sum(v[i].begin(),v[i].end(),v[i].begin());
	memset(f[1],0x1f,sizeof(f[1]));
	f[1][0]=0;
	for(int i=4;i>=0;i--)
	{
		if(v[i].size()==0)
			continue;
		// cout<<"i="<<i<<endl;
		memcpy(f[0],f[1],sizeof(f[0]));
		memset(f[1],0x1f,sizeof(f[1]));
		for(int r=0;r<i;r++)
		{
			for(int x=r,y=r;x<=4*n;x+=i)
			{
				while(((x-y)/i>(int)v[i].size()-1)||(y<x&&f[0][y+i]+v[i][(x-y-i)/i]<=f[0][y]+v[i][(x-y)/i]))
					y+=i;
				// cout<<"x="<<x<<" y="<<y<<" => "<<f[0][y]<<" + "<<v[i][(x-y)/i]<<endl;
				f[1][x]=min<int>(f[1][x],f[0][y]+v[i][(x-y)/i]);
			}
		}
		for(int x=4*n;x>=0;x--)
			f[1][x]=min<int>(f[1][x],f[1][x+1]);
		// for(int x=0;x<=4*n;x++)
		// 	cout<<"f "<<i<<" x="<<x<<" = "<<f[1][x]<<endl;
	}
	int ans=0;
	for(int x=0;x<=4*n;x++)
	{
		if(f[1][x]<=c5)
			ans=x;
	}
	cout<<ans+c1<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 10040kb

input:

5 57
9 14 31 18 27

output:

2

result:

wrong answer expected '8', found '2'