ログイン
新規登録
AtsuoCoder Waseda Tour Finals 2025
読込中…
Home
Tasks
Clar
Submissions
Standings
提出 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