QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#404598 | #2544. Flatland Currency | Zxc200611 | WA | 0ms | 10040kb | C++14 | 1.2kb | 2024-05-04 10:17:31 | 2024-05-04 10:17:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x1f1f1f1f1f1f1f1f;
int n,c,c1,c5;
int f[2][410000];
vector<int> v[5];
signed main()
{
cin>>n>>c;
c5=c/5,c1=c%5;
for(int i=0;i<=4;i++)
v[i]=vector<int>({0});
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
int x5=(x+4)/5,x1=((-x)%5+5)%5;
v[x1].push_back(x5);
}
for(int i=0;i<=4;i++)
partial_sum(v[i].begin(),v[i].end(),v[i].begin());
memset(f[1],0x1f,sizeof(f[1]));
f[1][0]=0;
for(int i=4;i>=0;i--)
{
if(v[i].size()==0)
continue;
// cout<<"i="<<i<<endl;
memcpy(f[0],f[1],sizeof(f[0]));
memset(f[1],0x1f,sizeof(f[1]));
for(int r=0;r<i;r++)
{
for(int x=r,y=r;x<=4*n;x+=i)
{
while(((x-y)/i>(int)v[i].size()-1)||(y<x&&f[0][y+i]+v[i][(x-y-i)/i]<=f[0][y]+v[i][(x-y)/i]))
y+=i;
// cout<<"x="<<x<<" y="<<y<<" => "<<f[0][y]<<" + "<<v[i][(x-y)/i]<<endl;
f[1][x]=min<int>(f[1][x],f[0][y]+v[i][(x-y)/i]);
}
}
for(int x=4*n;x>=0;x--)
f[1][x]=min<int>(f[1][x],f[1][x+1]);
// for(int x=0;x<=4*n;x++)
// cout<<"f "<<i<<" x="<<x<<" = "<<f[1][x]<<endl;
}
int ans=0;
for(int x=0;x<=4*n;x++)
{
if(f[1][x]<=c5)
ans=x;
}
cout<<ans+c1<<endl;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 10040kb
input:
5 57 9 14 31 18 27
output:
2
result:
wrong answer expected '8', found '2'