結果
問題 | No.1715 Dinner 2 |
ユーザー |
![]() |
提出日時 | 2021-10-22 22:03:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,723 bytes |
コンパイル時間 | 355 ms |
コンパイル使用メモリ | 50,816 KB |
実行使用メモリ | 7,108 KB |
最終ジャッジ日時 | 2024-09-23 05:34:08 |
合計ジャッジ時間 | 1,544 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
#include <stdio.h>#include <vector>#define MIN -1234567890std::vector< std::pair<int,int> > V[100010];std::pair<int,int> x[100010],y[100010];std::pair<int,int> W[1010];int main(){int a,b;scanf("%d%d",&a,&b);for(int i=1;i<=a;i++){int c,d;scanf("%d%d",&c,&d);V[c].push_back(std::make_pair(d-c,i));W[i] = std::make_pair(c,d);}std::pair<int,int> max1 = std::make_pair(MIN,0);std::pair<int,int> max2 = max1;for(int i=0;i<=100000;i++){for(int j=0;j<V[i].size();j++){if(max1.first <=V[i][j].first) max2 = max1, max1 = V[i][j];else if(max2.first <= V[i][j].first) max2 = V[i][j];}x[i] = max1, y[i] = max2;}long long int min = MIN, max = 0;long long int ans = MIN;while(min<=max){long long int h = (min+max)/2;int prev = -1;long long int s = -h;for(int i=1;i<=b-2;i++){long long int t = s<100000?s:100000;if(x[t].second==0){max = h-1;goto u;}else if(prev==x[t].second){if(y[t].second==0){max = h-1;goto u;}else{s += (y[t].first);prev = y[t].second;}}else{s += (x[t].first);prev = x[t].second;}}for(int i=1;i<=a;i++){if(i==prev) continue;if(s<W[i].first) continue;long long int s2 = s + (W[i].second-W[i].first);if(s2>100000){ans = h;min = h+1;goto u;}else if(s2<0);else if(x[s2].second==0);else{if(x[s2].second==i){if(y[s2].second==0);else{ans = h;min = h+1;goto u;}}else{ans = h;min = h+1;goto u;}}}max = h-1;u:;}printf("%lld",ans);}