QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#605 | #51766 | #21689. 【NOIP Round #2】找零 | ship2077 | feecle6418 | Success! | 2024-04-26 19:08:38 | 2024-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'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#51766 | #21689. 【NOIP Round #2】找零 | feecle6418 | 97 | 44ms | 24292kb | C++14 | 1.1kb | 2022-10-03 21:49:33 | 2024-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;
}