結果

問題 No.1122 Plane Tickets
ユーザー e869120e869120
提出日時 2020-07-02 20:40:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,749 bytes
コンパイル時間 696 ms
コンパイル使用メモリ 68,596 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-23 17:34:23
合計ジャッジ時間 1,964 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 1 ms
6,940 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 1 ms
6,944 KB
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 2 ms
6,940 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 2 ms
6,940 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 2 ms
6,944 KB
testcase_37 AC 2 ms
6,940 KB
testcase_38 AC 2 ms
6,944 KB
testcase_39 AC 2 ms
6,940 KB
testcase_40 AC 2 ms
6,940 KB
testcase_41 AC 2 ms
6,940 KB
testcase_42 AC 2 ms
6,940 KB
testcase_43 AC 2 ms
6,940 KB
testcase_44 AC 2 ms
6,944 KB
testcase_45 AC 2 ms
6,940 KB
testcase_46 AC 2 ms
6,940 KB
testcase_47 AC 2 ms
6,940 KB
testcase_48 AC 2 ms
6,944 KB
testcase_49 AC 2 ms
6,940 KB
testcase_50 AC 2 ms
6,944 KB
testcase_51 AC 2 ms
6,948 KB
testcase_52 AC 2 ms
6,940 KB
testcase_53 AC 2 ms
6,944 KB
testcase_54 AC 2 ms
6,944 KB
testcase_55 AC 2 ms
6,944 KB
testcase_56 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cassert>
#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;
	assert(0LL <= A && A <= 1000000000000000LL);
	assert(0LL <= B && B <= 1000000000000000LL);
	assert(0LL <= C && C <= 1000000000000000LL);
	assert(0LL <= D && D <= 1000000000000000LL);
	assert(0LL <= E && E <= 1000000000000000LL);
	cout << solve(A, B, C, D, E) << endl;
	return 0;
}
0