#968924 (C++17) No.1715 Dinner 2

• 問題: No.1715 Dinner 2
• ユーザー: 00 Sakuda
• 提出日時: 2024-04-03 20:18:53
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 95 ms / 2,000 ms
• コード長: 1,183 bytes
• コンパイル時間: 1,999 ms
• コンパイル使用メモリ: 205,932 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-01 00:03:40
• 合計ジャッジ時間: 4,012 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	77 ms; 5,248 KB
testcase_12	AC	62 ms; 5,248 KB
testcase_13	AC	53 ms; 5,248 KB
testcase_14	AC	60 ms; 5,248 KB
testcase_15	AC	61 ms; 5,248 KB
testcase_16	AC	58 ms; 5,248 KB
testcase_17	AC	37 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	3 ms; 5,248 KB
testcase_20	AC	3 ms; 5,248 KB
testcase_21	AC	2 ms; 5,248 KB
testcase_22	AC	2 ms; 5,248 KB
testcase_23	AC	3 ms; 5,248 KB
testcase_24	AC	3 ms; 5,248 KB
testcase_25	AC	10 ms; 5,248 KB
testcase_26	AC	7 ms; 5,248 KB
testcase_27	AC	7 ms; 5,248 KB
testcase_28	AC	8 ms; 5,248 KB
testcase_29	AC	9 ms; 5,248 KB
testcase_30	AC	8 ms; 5,248 KB
testcase_31	AC	8 ms; 5,248 KB
testcase_32	AC	91 ms; 5,248 KB
testcase_33	AC	94 ms; 5,248 KB
testcase_34	AC	92 ms; 5,248 KB
testcase_35	AC	95 ms; 5,248 KB
testcase_36	AC	2 ms; 5,248 KB
testcase_37	AC	2 ms; 5,248 KB
testcase_38	AC	2 ms; 5,248 KB

ソースコード

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace atcoder;
using namespace std;
using mint = modint;
using ll = long long;
ll INF = (1LL << 60);
int main() {
	int N, D;cin >> N >> D;
	vector<ll> P(N + 1, 0), Q(N + 1, 0);
	for (int i = 1;i <= N;i++) cin >> P[i] >> Q[i];
	ll ok = -(1e9 + 100);
	ll ng = 1e9 + 100;
	while (ng - ok > 1) {
		ll X = (ok + ng) / 2;
		vector<ll> dp(N + 2, -INF);
		for (int i = 1;i <= N;i++) if (-P[i] >= X) dp[i] = Q[i] - P[i];
		vector<ll> rmx(N + 1, -INF), lmx(N + 2, -INF);
		for (int i = 1;i <= N;i++) rmx[i] = max(rmx[i - 1], dp[i]);
		for (int i = N;i >= 1;i--) lmx[i] = max(lmx[i + 1], dp[i]);
		for (int i = 2;i <= D;i++) {
			vector<ll> ndp(N + 2, -INF);
			for (int j = 1;j <= N;j++) {
				ll mx = max(rmx[j - 1], lmx[j + 1]);
				if (mx == -INF) continue;
				if (mx - P[j] >= X) {
					ndp[j] = mx + Q[j] - P[j];
				}
			}
			swap(dp, ndp);
			for (int i = 1;i <= N;i++) rmx[i] = max(rmx[i - 1], dp[i]);
			for (int i = N;i >= 1;i--) lmx[i] = max(lmx[i + 1], dp[i]);
		}
		bool ret = false;
		for (int i = 1;i <= N;i++) if (dp[i] >= X) ret = true;
		if (ret) {
			ok = X;
		} else  {
			ng = X;
		}
	}
	cout << ok << endl;
}