結果

問題 No.1122 Plane Tickets
コンテスト
ユーザー e869120
提出日時 2020-07-22 21:12:43
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 1,500 bytes
コンパイル時間 583 ms
コンパイル使用メモリ 68,544 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-23 17:34:33
合計ジャッジ時間 1,944 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
using namespace std;

long long sims(long long a, long long b, long long c, long long d, long long e) {
	long long t1 = max(a, 0LL); a -= t1; b -= t1;
	long long t2 = max(b, 0LL); b -= t2; c -= t2;
	long long t3 = max(c, 0LL); c -= t3; d -= t3;
	long long t4 = max(d, 0LL); d -= t4; e -= t4;
	long long t5 = max(e, 0LL);
	return t1 + t2 + t3 + t4 + t5;
}

long long solve2(long long a, long long b, long long c, long long d, long long e) {
	long long L = 0, R = max({ a, e, 0LL }) + 1LL, c1, c2, Current = (1LL << 60);
	for (int i = 0; i < 80; i++) {
		c1 = (L + L + R) / 3LL;
		c2 = (L + R + R) / 3LL;
		long long v1 = sims(a - c1, b, c, d, e - c1) + c1;
		long long v2 = sims(a - c2, b, c, d, e - c2) + c2;
		Current = min({ Current, v1, v2 });
		if (v1 < v2) { R = c2; }
		else { L = c1; }
	}
	for (long long i = c1 - 2; i <= c2 + 3; i++) {
		if (i < 0) continue;
		long long v1 = sims(a - i, b, c, d, e - i) + i;
		Current = min(Current, v1);
	}
	return Current;
}

long long solve(long long a, long long b, long long c, long long d, long long e) {
	long long cl = 0, cr = (a + b + c + d + e) / 3LL + 1LL, cm, maxn = 0;
	for (int i = 0; i < 60; i++) {
		cm = (cl + cr) / 2LL;
		long long val = solve2(cm - a, cm - b, cm - c, cm - d, cm - e);
		if (val <= cm) { cl = cm; maxn = max(maxn, cm); }
		else { cr = cm; }
	}
	return maxn;
}

int main() {
	long long A, B, C, D, E;
	cin >> A >> B >> C >> D >> E;
	cout << solve(A, B, C, D, E) << endl;
	return 0;
}
0