結果
問題 | No.1122 Plane Tickets |
ユーザー |
![]() |
提出日時 | 2020-07-02 20:38:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,500 bytes |
コンパイル時間 | 776 ms |
コンパイル使用メモリ | 67,344 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 17:34:20 |
合計ジャッジ時間 | 2,031 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 55 |
ソースコード
#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;}