QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#602#69180#21689. 【NOIP Round #2】找零ship2077sjcxSuccess!2024-04-26 17:42:422024-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'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69180#21689. 【NOIP Round #2】找零sjcx97 17ms12028kbC++141.9kb2022-12-24 21:47:462024-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;
}