結果
問題 | No.1715 Dinner 2 |
ユーザー |
|
提出日時 | 2021-10-22 22:09:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 1,079 bytes |
コンパイル時間 | 2,319 ms |
コンパイル使用メモリ | 198,104 KB |
最終ジャッジ日時 | 2025-01-25 03:45:58 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N, D; cin >> N >> D; vector<int> P(N), Q(N); for(int i = 0; i < N; i++) cin >> P[i] >> Q[i]; int ub = 0, lb = -1000000000; int INF = 2000000000; while(ub - lb > 1){ int mid = (ub + lb) / 2; vector<vector<int>> dp(D, vector<int>(N, -INF)); bool f = false; for(int i = 0; i < N; i++){ if(-P[i] >= mid) dp[0][i] = -P[i] + Q[i]; } for(int i = 0; i < D - 1; i++){ vector<int> L(N + 1, -INF), R(N + 1, -INF); for(int j = 0; j < N; j++){ L[j + 1] = max(L[j], dp[i][j]); R[N - 1 - j] = max(R[N - j], dp[i][N - 1 - j]); } for(int j = 0; j < N; j++){ int t = max(R[j + 1], L[j]); if(t - P[j] >= mid) dp[i + 1][j] = t - P[j] + Q[j]; } } for(int i = 0; i < N; i++){ if(dp[D - 1][i] != -INF) f = true; } if(f) lb = mid; else ub = mid; } cout << lb << endl; }