結果
問題 |
No.3297 Bake Cookies
|
ユーザー |
|
提出日時 | 2025-10-07 12:59:13 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 1,458 bytes |
コンパイル時間 | 3,224 ms |
コンパイル使用メモリ | 278,620 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-10-07 12:59:23 |
合計ジャッジ時間 | 9,403 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; bool calc(ll num, const vector<ll>& mem, ll N, ll T) { // p: 吸収できる個数合計、 q: 過剰な個数合計 __int128 p = 0, q = 0; if (T == 0) { // 安全策:T==0なら意味合いにより処理を変える必要あり // ここでは T==0 は不正入力想定。必要なら別処理を書く。 return false; } for (ll i = 0; i < N; ++i) { if (mem[i] <= num) { p += (num - mem[i]) / T; } else { q += (mem[i] - num); } if (p >= q && q > 0) { // 早期判定(pが既にq以上ならtrue) // 注意: qが0のときは最後にチェックすれば良い return true; } } return q <= p; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N, M, T; if (!(cin >> N >> M >> T)) return 0; vector<ll> mem(N, 0); for (ll i = 0; i < M; ++i) { ll a; cin >> a; if (1 <= a && a <= N) mem[a - 1] += 1; // 範囲外入力があるならここで対処 } ll left = -1; // 不成立の下限 ll right = 1000000000000000000LL; // 十分大きい上限 (1e18) while (left + 1 < right) { ll mid = left + (right - left) / 2; if (calc(mid, mem, N, T)) right = mid; else left = mid; } cout << right << '\n'; return 0; }