QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22409 | #2544. Flatland Currency | George_Plover | WA | 1ms | 3748kb | C++20 | 2.5kb | 2022-03-09 17:30:03 | 2022-04-30 01:02:29 |
Judging History
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'