結果
問題 | 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 -1234567890 std::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); }