結果
問題 | No.1211 円環はお断り |
ユーザー |
|
提出日時 | 2020-08-30 17:16:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,926 ms / 2,000 ms |
コード長 | 1,537 bytes |
コンパイル時間 | 2,454 ms |
コンパイル使用メモリ | 102,044 KB |
最終ジャッジ日時 | 2025-01-14 00:54:23 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#include <iostream> #include <numeric> #include <vector> template <class T> std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); } using lint = long long; void solve() { int n, k; std::cin >> n >> k; std::vector<lint> xs(n); for (auto& x : xs) std::cin >> x; lint ok = 0, ng = std::accumulate(xs.begin(), xs.end(), 0LL) + 1; while (ng - ok > 1) { lint mid = (ok + ng) / 2; auto to = vec(20, vec(n, 0LL)); { int r = 0; lint sum = 0; for (int l = 0; l < n; ++l) { while (sum < mid) { sum += xs[r % n]; ++r; } to[0][l] = r - l; sum -= xs[l]; } } for (int d = 0; d + 1 < 20; ++d) { for (int i = 0; i < n; ++i) { to[d + 1][i] = to[d][i] + to[d][(i + to[d][i]) % n]; } } bool judge = false; for (int s = 0; s < n; ++s) { int v = s; lint sum = 0; for (int d = 0; d < 20; ++d) { if ((~k >> d) & 1) continue; sum += to[d][v]; (v += to[d][v]) %= n; } if (sum <= n) judge = true; } if (judge) { ok = mid; } else { ng = mid; } } std::cout << ok << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }