提出 798c3b4a-4da2-40f2-b6b0-1ad582175555

コード

#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 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;
}
void output(int n,int m,ll h,vector<int>d,vector<int>t,ofstream&ofs){
	ofs<<n<<' '<<m<<' '<<h<<endl;
	for(int i=0;i<n;i++)
		ofs<<d[i]<<' '<<t[i]<<endl;
}
void generater(){
	random_device seed;
	mt19937 rand(seed());
	for(int a=1;a<=2;a++){
		for(int b=1;b<=(a==1?6:7);b++){
			int n,m;
			ll h;
			vector<int>d,t;
			if(a==1&&b==1){
				n=3,m=2,h=4;
				d={1,3,5},t={15,10,12};
			}
			if(a==1&&b==2){
				n=3,m=2,h=4;
				d={2,3,5},t={15,10,12};
			}
			if(a==1&&b==3){
				uniform_int_distribution<>d1(1,20);
				n=d1(rand);
				uniform_int_distribution<>d2(1,n);
				m=d2(rand);
				uniform_int_distribution<ll>d3(1,1000000000000000000);
				h=d3(rand);
				d.resize(n),t.resize(n);
				for(int i=0;i<n;i++){
					uniform_int_distribution<>d4(1,1000000000);
					d[i]=d4(rand),t[i]=d4(rand);
				}
			}
			if(a==1&&b==4){
				n=20;
				m=20;
				h=1000000000000000000;
				d.resize(n),t.resize(n);
				for(int i=0;i<n;i++)
					d[i]=1000000000,t[i]=1000000000;
			}
			if(a==1&&b==5){
				uniform_int_distribution<>d1(1,20);
				n=d1(rand);
				uniform_int_distribution<>d2(1,n);
				m=d2(rand);
				d.resize(n),t.resize(n);
				for(int i=0;i<n;i++){
					uniform_int_distribution<>d4(1,1000000000);
					d[i]=d4(rand),t[i]=d4(rand);
				}
				vector<int>sd=d;
				sort(sd.begin(),sd.end());
				ll tmp=accumulate(sd.begin(),sd.begin()+m,0ll);
				uniform_int_distribution<ll>d3(1,tmp-1);
				h=d3(rand);
			}
			if(a==1&&b==6){
				do{
					uniform_int_distribution<>d1(1,20);
					n=d1(rand);
					uniform_int_distribution<>d2(1,n);
					m=d2(rand);
					d.resize(n),t.resize(n);
					for(int i=0;i<n;i++){
						uniform_int_distribution<>d4(1,1000000000);
						d[i]=d4(rand),t[i]=d4(rand);
					}
					vector<int>sd=d;
					sort(sd.begin(),sd.end());
					ll tmp=accumulate(sd.begin(),sd.begin()+n,0ll);
					uniform_int_distribution<ll>d3(1,tmp);
					h=d3(rand);
					cout<<solve(n,m,h,d,t)<<endl;
					cout<<fakesolve(n,m,h,d,t)<<endl;
					cout<<fakesolve2(n,m,h,d,t)<<endl;
					cout<<endl;
				}while(solve(n,m,h,d,t)==fakesolve(n,m,h,d,t)||solve(n,m,h,d,t)==fakesolve2(n,m,h,d,t));
			}
			if(a==2&&(b==1||b==2)){
				uniform_int_distribution<>d1(1,200000);
				n=d1(rand);
				uniform_int_distribution<>d2(1,n);
				m=d2(rand);
				uniform_int_distribution<ll>d3(1,1000000000000000000);
				h=d3(rand);
				d.resize(n),t.resize(n);
				for(int i=0;i<n;i++){
					uniform_int_distribution<>d4(1,1000000000);
					d[i]=d4(rand),t[i]=d4(rand);
				}
			}
			if(a==2&&b==3){
				n=200000;
				m=200000;
				h=1000000000000000000;
				d.resize(n),t.resize(n);
				for(int i=0;i<n;i++)
					d[i]=1000000000,t[i]=1000000000;
			}
			if(a==2&&(b==4||b==5)){
				uniform_int_distribution<>d1(1,200000);
				n=d1(rand);
				uniform_int_distribution<>d2(1,n);
				m=d2(rand);
				d.resize(n),t.resize(n);
				for(int i=0;i<n;i++){
					uniform_int_distribution<>d4(1,1000000000);
					d[i]=d4(rand),t[i]=d4(rand);
				}
				vector<int>sd=d;
				sort(sd.begin(),sd.end());
				ll tmp=accumulate(sd.begin(),sd.begin()+m,0ll);
				uniform_int_distribution<ll>d3(1,tmp-1);
				h=d3(rand);
			}
			if(a==2&&(b==6||b==7)){
				do{
					uniform_int_distribution<>d1(1,200000);
					n=d1(rand);
					uniform_int_distribution<>d2(1,n);
					m=d2(rand);
					d.resize(n),t.resize(n);
					for(int i=0;i<n;i++){
						uniform_int_distribution<>d4(1,1000000000);
						d[i]=d4(rand),t[i]=d4(rand);
					}
					vector<int>sd=d;
					sort(sd.begin(),sd.end());
					ll tmp=accumulate(sd.begin(),sd.begin()+n,0ll);
					uniform_int_distribution<ll>d3(1,tmp);
					h=d3(rand);
					cout<<solve(n,m,h,d,t)<<endl;
					cout<<fakesolve(n,m,h,d,t)<<endl;
					cout<<fakesolve2(n,m,h,d,t)<<endl;
					cout<<endl;
				}while(solve(n,m,h,d,t)==fakesolve(n,m,h,d,t)||solve(n,m,h,d,t)==fakesolve2(n,m,h,d,t));
			}
			filesystem::create_directory(to_string(a)+'_'+to_string(b));
			ofstream in(to_string(a)+'_'+to_string(b)+"/stdin.txt");
			ofstream out(to_string(a)+'_'+to_string(b)+"/stdout.txt");
			valid(n,m,h,d,t);
			if(a==1)
				assert(n<=20);
			output(n,m,h,d,t,in);
			out<<solve(n,m,h,d,t)<<endl;
		}
	}
}
int main(){
	//generater();
	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<<solve(n,m,h,d,t)<<endl;
}
結果

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