QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#604#53348#21689. 【NOIP Round #2】找零ship2077chenshigeFailed.2024-04-26 19:07:552024-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"

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53348#21689. 【NOIP Round #2】找零chenshige100 ✓24ms6460kbC++201.5kb2022-10-04 23:38:312024-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;
}