結果

問題 No.1715 Dinner 2
コンテスト
ユーザー square1001
提出日時 2021-10-22 23:30:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 779 bytes
コンパイル時間 585 ms
コンパイル使用メモリ 69,240 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 08:05:09
合計ジャッジ時間 1,958 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <iostream>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	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 l = 0, r = (1 << 29);
	while (r - l > 1) {
		int m = (l + r) >> 1;
		int genki = 0, prechoice = -1;
		bool flag = true;
		for (int i = 0; i < D; ++i) {
			int optchoice = -1, optscore = -(1 << 30);
			for (int j = 0; j < N; ++j) {
				if (j != prechoice && genki + P[j] <= m && optscore < Q[j] - P[j]) {
					optchoice = j;
					optscore = Q[j] - P[j];
				}
			}
			if (optchoice == -1) {
				flag = false;
				break;
			}
			genki -= optscore;
			prechoice = optchoice;
		}
		if (flag) r = m;
		else l = m;
	}
	cout << -r << endl;
	return 0;
}
0