QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22409#2544. Flatland CurrencyGeorge_PloverWA 1ms3748kbC++202.5kb2022-03-09 17:30:032022-04-30 01:02:29

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:02:29]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3748kb
  • [2022-03-09 17:30:03]
  • Submitted

answer

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 110000
#define LL long long
using namespace std;
int n;
LL m;
int a[MAXN];
int v[MAXN];
LL q[5][MAXN];
int loc[5];
int cnt[5];
int main()
{
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]%5)
        {
            v[i]=5-a[i]%5;
            a[i]+=v[i];
            q[v[i]][++loc[v[i]]]=a[i];
        }
    }
    int ans=m%5;
    m-=ans;

    for(int i=1;i<=4;i++){
        sort(q[i]+1,q[i]+loc[i]+1);
        cnt[i]=1;
    }

    LL w=m;
    while(1)
    {
        bool flag=0;
        int num;
        for(int i=1;i<=4;i++)
        {
            if(w<q[i][cnt[i]] || cnt[i]>loc[i])continue;
            else if(!flag)
            {
                num=i;flag=1;
            }
            else if(1ll * i * q[num][cnt[num]] <= 1ll * num * q[i][cnt[i]])
            {
                num=i;
            }
        }
        if(!flag)break;
        w-=q[num][cnt[num]++];
    }
    for(int i=1;i<=4;i++)cnt[i]--;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=loc[i];j++)
            q[i][j]+=q[i][j-1];
    int out=ans;
    for(int i=0;i<=min(11,loc[1]);i++)
        for(int j=0;j<=min(5,loc[2]);j++)
            for(int k=0;k<=min(3,loc[3]);k++)
                for(int l=0;l<=min(2,loc[4]);l++)
                {
                    int v = i + 2*j +3*k +4*l;
                    LL sp = q[1][i] + q[2][j] + q[3][k] + q[4][l];
                    LL t=m-sp;
                    while(1){
                        bool flag=0;
                        int num;
                        cnt[1]=i;cnt[2]=j;cnt[3]=k;cnt[4]=l;
                        for(int x=1;x<=4;x++)
                        {
                            if(cnt[x]+12/x>loc[x] || t<q[x][cnt[x]+12/x]-q[x][cnt[x]])continue;
                            else if(!flag)
                            {
                                num=x;flag=1;
                            }
                            else if(q[num][cnt[num]+12/num]-q[num][cnt[num]] <= q[x][cnt[x]+12/x]-q[x][cnt[x]])
                            {
                                num=x;
                            }
                        }
                        if(!flag)break;
                        t-=q[num][cnt[num]+12/num]-q[num][cnt[num]];
                        v+=12;
                        cnt[num]+=12/num;
                    }
                    out=max(out,v+ans);
                }
    cout<<out<<endl;
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3748kb

input:

5 57
9 14 31 18 27

output:

13

result:

wrong answer expected '8', found '13'