QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404611#2544. Flatland CurrencyZxc200611WA 4ms9876kbC++141.6kb2024-05-04 10:41:292024-05-04 10:41:31

Judging History

This is the latest submission verdict.

  • [2024-05-04 10:41:31]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 9876kb
  • [2024-05-04 10:41:29]
  • Submitted

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];
void devideConquer(int i,int r,int ql,int qr,int al,int ar)
{
	if(ql>qr)
		return;
	// cout<<"DevideConquer q=["<<ql<<","<<qr<<"] a=["<<al<<","<<ar<<"]"<<endl;
	int qm=((ql/i+qr/i)/2)*i+r;
	// cout<<"qm="<<qm<<endl;
	int pos=-1;
	for(int x=max<int>(al,qm-i*(v[i].size()-1));x<=min<int>(qm,ar);x+=i)
	{
		if(pos==-1||f[0][x]+v[i][(qm-x)/i]<=f[0][pos]+v[i][(qm-pos)/i])
			pos=x;
	}
	assert(pos!=-1);
	f[1][qm]=f[0][pos]+v[i][(qm-pos)/i];
	devideConquer(i,r,ql,qm-i,al,pos);
	devideConquer(i,r,qm+i,qr,pos,ar);
}
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>=1;i--)
	for(int i=1;i<=4;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++)
			devideConquer(i,r,r,((4*n-r)/i)*i+r,r,((4*n-r)/i)*i+r);
		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++)
	{
		// cout<<"f "<<x<<" = "<<f[1][x]<<endl;
		if(f[1][x]<=c5)
			ans=x;
	}
	cout<<ans+c1<<endl;
}

详细

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 9876kb

input:

5 57
9 14 31 18 27

output:

i=1
i=2
i=3
i=4
8

result:

wrong output format i=1 is not a valid integer