QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#602 | #69180 | #21689. 【NOIP Round #2】找零 | ship2077 | sjcx | Success! | 2024-04-26 17:42:42 | 2024-04-26 17:42:43 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 11768kb
input:
9 5 19 14 13 1 19 12 17 9 18
output:
0
result:
wrong answer 1st words differ - expected: '4', found: '0'
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69180 | #21689. 【NOIP Round #2】找零 | sjcx | 97 | 17ms | 12028kb | C++14 | 1.9kb | 2022-12-24 21:47:46 | 2024-04-26 17:44:36 |
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<vector>
#include<map>
#include<queue>
#include<set>
using namespace std;
#define re int
#define ll long long
inline int read(){
int x=0,ff=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
return x*ff;
}
int n,ss,w[100005],tot,cnt;
ll X,f[400005],g[400005],a[100005],p[100005],q[100005],d[100005];
void solve(ll *f,int x,int y){
int now=0,u,v;
for(re i=y;i<=(n<<2);i+=y){
for(re j=0;j<=1;j++){
u=now+j;v=max((i-u*x)/y,0);
if(u>tot||v>cnt)continue;
if(f[i]>=p[u]+q[v]){
f[i]=p[u]+q[v];now=u;
}
}
}
}
signed main(){
cin>>n>>X;ss=X%5;X-=ss;
for(re i=1;i<=n;i++){
a[i]=read();w[i]=a[i]%5?5-a[i]%5:0;
a[i]+=w[i];
}
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
f[0]=g[0]=0;
for(re i=1;i<=n;i++)
if(w[i]==4)d[++tot]=a[i];
sort(d+1,d+tot+1);
for(re i=1;i<=tot;i++)p[i]=p[i-1]+d[i];
for(re i=1;i<=n;i++)
if(w[i]==2)d[++cnt]=a[i];
sort(d+1,d+cnt+1);
for(re i=1;i<=cnt;i++)q[i]=q[i-1]+d[i];
solve(f,4,2);
tot=cnt=0;
for(re i=1;i<=n;i++)
if(w[i]==3)d[++tot]=a[i];
sort(d+1,d+tot+1);
for(re i=1;i<=tot;i++)p[i]=p[i-1]+d[i];
for(re i=1;i<=n;i++)
if(w[i]==1)d[++cnt]=a[i];
sort(d+1,d+cnt+1);
for(re i=1;i<=cnt;i++)q[i]=q[i-1]+d[i];
solve(g,3,1);
int l=0,r=n<<2,mid;
while(l<=r){
mid=(l+r)>>1;bool ok=0;
for(re i=0;i<=mid;i++){
if(f[i]+g[mid-i]<=X){ok=1;break;}
}
if(ok)l=mid+1;
else r=mid-1;
}
cout<<l+ss-1<<endl;
return 0;
}