QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414321#2544. Flatland CurrencyKevin5307TL 0ms3824kbC++231.5kb2024-05-18 20:59:522024-05-18 20:59:53

Judging History

你现在查看的是最新测评结果

  • [2024-05-18 20:59:53]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3824kb
  • [2024-05-18 20:59:52]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll val[1004];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	ll x;
	cin>>n>>x;
	int ans=x%5;
	x/=5;
	vector<pii> vec;
	while(n--)
	{
		int y;
		cin>>y;
		if(y%5==0) continue;
		vec.pb(y/5+1,5-y%5); 
	}
	sort(ALL(vec),[&](pii a,pii b)
	{
		return 1ll*a.second*b.first>1ll*a.first*b.second;
	});
	int cur=0;
	while(cur<sz(vec)&&vec[cur].first<=x)
	{
		x-=vec[cur].first;
		ans+=vec[cur].second;
	}
	int lim=min(cur,10);
	while(lim--)
	{
		cur--;
		x+=vec[cur].first;
		ans-=vec[cur].second;
	}
	memset(val,0x3f,sizeof(val));
	val[0]=0;
	for(int i=cur;i<sz(vec);i++)
		for(int j=53-vec[i].second;j>=0;j--)
			val[j+vec[i].second]=min(val[j+vec[i].second],val[j]+vec[i].first);
	ll mx=0;
	for(int j=0;j<54;j++)
		if(val[j]<=x)
			mx=j;
	cout<<ans+mx<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

input:

5 57
9 14 31 18 27

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

4 50
11 11 11 11

output:

12

result:

ok answer is '12'

Test #3:

score: -100
Time Limit Exceeded

input:

100000 89648823509660
921733427 402270498 51157221 585477094 435728758 913951087 580580944 557082810 585086423 837912728 799129405 867009344 751591136 714946046 464999915 256043168 416678301 183246216 569365122 479031618 435168577 31068363 903791719 497652990 960987871 223120213 395437892 112869678 ...

output:


result: