QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#604 | #53348 | #21689. 【NOIP Round #2】找零 | ship2077 | chenshige | Failed. | 2024-04-26 19:07:55 | 2024-04-26 19:07:57 |
Details
Extra Test:
Accepted
time: 1ms
memory: 3824kb
input:
4 637054900 909892 46637 294307 506475
output:
9
result:
ok "9"
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#53348 | #21689. 【NOIP Round #2】找零 | chenshige | 100 ✓ | 24ms | 6460kb | C++20 | 1.5kb | 2022-10-04 23:38:31 | 2024-04-26 19:09:10 |
answer
// Nothing is Given, Everything is Earned.
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
LL n,X; cin>>n>>X;
LL charge=X%5; X/=5;
vector<vector<LL>> r(5);
for(int i=0;i<n;i++)
{
int x; cin>>x;
if(x%5) r[5-x%5].push_back(x/5+1);
}
vector<pair<int, int>> score;
for(int i=1;i<=4;i++)
{
sort(r[i].begin(),r[i].end());
for(int a=0;a<r[i].size();a++)
score.push_back({i, a});
}
sort(score.begin(),score.end(),[&](pair<int,int> x,pair<int,int> y)
{
LL cx=r[x.first][x.second];
LL cy=r[y.first][y.second];
return cx*y.first<cy*x.first;
});
vector<int> need(5,0);
LL nleft=X;
for(auto [k,loc]:score)
{
if(nleft>=r[k][loc])
{
nleft-=r[k][loc];
need[k]++;
}
else break;
}
vector<vector<LL>> psums(5);
for(int i=0;i<=4;i++)
{
vector<LL> psum(r[i].size()+1,0);
partial_sum(r[i].begin(),r[i].end(),++psum.begin());
psums[i]=psum;
}
int res = 0;
const int B = 10;
for(int l1=-B;l1<=B;l1++) for(int l2=-B;l2<=B;l2++)
for(int l3=-B;l3<=B;l3++) for(int l4=-B;l4<=B;l4++)
{
int t1=l1+need[1],t2=l2+need[2],t3=l3+need[3],t4=l4+need[4];
if(t1<0 || t2<0 || t3<0 || t4<0) continue;
if(t1>r[1].size() || t2>r[2].size() || t3>r[3].size() || t4>r[4].size()) continue;
LL cost=psums[1][t1]+ psums[2][t2]+psums[3][t3]+psums[4][t4];
if(cost<=X) res=max(res,1*t1+2*t2+3*t3+4*t4);
}
cout<<res+charge<<'\n';
return 0;
}