提出 154f1fd6-8f02-4c80-b77c-d642477d6267

コード

#include<bits/stdc++.h>
#include<filesystem>
using namespace std;
using ll=long long;
const ll inf=1e18;
void valid(int n,int m,ll h,vector<int>d,vector<int>t){
	assert(1<=m&&m<=n&&n<=200000);
	assert(1<=h&&h<=1000000000000000000);
	for(int i=0;i<n;i++){
		assert(1<=d[i]&&d[i]<=1000000000);
		assert(1<=t[i]&&t[i]<=1000000000);
	}
}
int solve(int n,int m,ll h,vector<int>d,vector<int>t){
	int ng=0,ok=1000000001;
	while(ok-ng>1){
		int mid=(ng+ok)/2;
		vector<int>vec;
		for(int i=0;i<n;i++)
			if(t[i]<=mid)
				vec.push_back(d[i]);
		if(vec.size()<m){
			ng=mid;
			continue;
		}
		sort(vec.begin(),vec.end());
		ll sum=0;
		for(int i=0;i<m;i++)
			sum+=vec[i];
		if(sum<=h)
			ok=mid;
		else
			ng=mid;
	}
	if(ok==1000000001)
		ok=-1;
	return ok;
}
int solve2(int n,int m,ll h,vector<int>d,vector<int>t){
	vector<pair<int,int>>td(n);
	for(int i=0;i<n;i++)
		td[i]={t[i],d[i]};
	sort(td.begin(),td.end());
	for(int i=0;i<n;i++){
		t[i]=td[i].first;
		d[i]=td[i].second;
	}
	priority_queue<int>pque;
	ll tmp=0;
	for(int i=0;i<m;i++){
		pque.push(d[i]);
		tmp+=d[i];
	}
	if(tmp<=h)
		return t[m-1];
	for(int i=m;i<n;i++){
		pque.push(d[i]);
		tmp+=d[i];
		tmp-=pque.top();
		pque.pop();
		if(tmp<=h)
			return t[i];
	}
	return -1;
}
int fakesolve(int n,int m,ll h,vector<int>d,vector<int>t){
	vector<pair<int,int>>dt(n);
	for(int i=0;i<n;i++)
		dt[i]={d[i],t[i]};
	sort(dt.begin(),dt.end());
	for(int i=0;i<n;i++){
		d[i]=dt[i].first;
		t[i]=dt[i].second;
	}
	int cnt=0,mx=0;
	ll sum=0;
	for(int i=0;i<n;i++){
		if(sum+d[i]<=h){
			sum+=d[i];
			mx=max(mx,t[i]);
			cnt++;
			if(cnt==m)
				return mx;
		}
	}
	return -1;
}
int fakesolve2(int n,int m,ll h,vector<int>d,vector<int>t){
	vector<pair<int,int>>td(n);
	for(int i=0;i<n;i++)
		td[i]={t[i],d[i]};
	sort(td.begin(),td.end());
	for(int i=0;i<n;i++){
		t[i]=td[i].first;
		d[i]=td[i].second;
	}
	int cnt=0,mx=0;
	ll sum=0;
	for(int i=0;i<n;i++){
		if(sum+d[i]<=h){
			sum+=d[i];
			mx=max(mx,t[i]);
			cnt++;
			if(cnt==m)
				return mx;
		}
	}
	return -1;
}
int fakesolve3(int n,int m,ll h,vector<int>d,vector<int>t){
	vector<int>sd=d;
	sort(sd.begin(),sd.end());
	if(accumulate(sd.begin(),sd.begin()+m,0ll)>h)
		return -1;
	int f2=fakesolve2(n,m,h,d,t);
	if(f2==-1)
		return fakesolve(n,m,h,d,t);
	return f2;
}
int main(){
	int n,m;
	ll h;
	cin>>n>>m>>h;
	vector<int>d(n),t(n);
	for(int i=0;i<n;i++)
	cin>>d[i]>>t[i];
	valid(n,m,h,d,t);
	cout<<solve2(n,m,h,d,t)<<endl;
}
結果

問題	点数	言語	結果	実行時間	メモリ
G - Contest	150	C++	AC	122 ms	9600 KiB