結果
問題 | 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;}