QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#605#51766#21689. 【NOIP Round #2】找零ship2077feecle6418Success!2024-04-26 19:08:382024-04-26 19:08:39

Details

Extra Test:

Wrong Answer
time: 2ms
memory: 12660kb

input:

4 637054900
909892 46637 294307 506475

output:

6

result:

wrong answer 1st words differ - expected: '9', found: '6'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51766#21689. 【NOIP Round #2】找零feecle641897 44ms24292kbC++141.1kb2022-10-03 21:49:332024-04-26 19:08:50

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
ll f[400005],g[400005],n,X,val[5][400005],m[5];
void Solve(int rem,int d,int l1,int r1,int l2,int r2){
	while(l1%d!=rem)l1++;
	while(r1%d!=rem&&r1>=0)r1--;
	if(l1>r1)return ;
	if(l2==r2){
		for(int i=l1;i<=r1;i+=d)if((i-l2)/d<=m[d])g[i]=f[l2]+val[d][(i-l2)/d];
		return ;
	}
	int mid=(l1+r1)/2,pos=r2;
	while(mid%d!=rem)mid--;
	ll mn=inf;
	for(int i=l2;i<=min(r2,mid);i+=d){
		if((mid-i)/d>m[d])continue;
		ll w=f[i]+val[d][(mid-i)/d];
		if(w<mn)mn=w,pos=i;
	}
	g[mid]=mn,Solve(rem,d,l1,mid-1,l2,pos),Solve(rem,d,mid+1,r1,pos,r2);
}
int main(){
	int tmp;
	cin>>n>>X,tmp=X%5,X-=X%5;
	memset(f,0x3f,sizeof(f)),f[0]=0;
	for(int i=1,x;i<=n;i++){
		scanf("%d",&x);
		int y=(5-x%5)%5;
		if(!y)continue;
		x+=y,val[y][++m[y]]=x;
	}
	for(int i=1;i<=4;i++){
		sort(val[i]+1,val[i]+m[i]+1);
		for(int j=1;j<=m[i];j++)val[i][j]+=val[i][j-1];
		memset(g,0x3f,sizeof(g));
		for(int j=0;j<i;j++)Solve(j,i,0,4*n,j,(4*n-j)/i*i+j);
		memcpy(f,g,sizeof(f));
	}
	int ans=0;
	for(int i=0;i<=4*n;i++)if(f[i]<=X)ans=i;
	cout<<ans+tmp;
}