結果
問題 | No.1211 円環はお断り |
ユーザー |
![]() |
提出日時 | 2020-08-30 14:58:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,232 bytes |
コンパイル時間 | 13,694 ms |
コンパイル使用メモリ | 284,092 KB |
最終ジャッジ日時 | 2025-01-13 22:19:43 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 TLE * 9 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")// Template#include <bits/stdc++.h>#define rep_override(x, y, z, name, ...) name#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)#define all(x) (x).begin(), (x).end()using namespace std;using ll = long long;constexpr int inf = 1001001001;constexpr ll INF = 3003003003003003003;template <typename T> inline bool chmin(T& x, const T& y) {if (x > y) {x = y; return 1;} return 0;}template <typename T> inline bool chmax(T& x, const T& y) {if (x < y) {x = y; return 1;} return 0;}struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;int main() {int n, k;cin >> n >> k;vector<ll> a(n);rep(i, n) cin >> a[i];vector<ll> b(2 * n);rep(i, n) b[i] = b[i + n] = a[i];ll s = 0;rep(i, n) s += a[i];vector<int> nxt(3 * n + 1, 3 * n);vector<vector<int>> vec(3 * n + 1, vector<int>(17));auto judge = [&](ll x) -> bool {if (s < x) return false;{int now = 0; ll sum = 0;while (sum < x) {sum += b[now]; ++now;}nxt[0] = now;rep(i, 1, n) {sum -= b[i - 1];while (sum < x) {sum += b[now]; ++now;}nxt[i] = now;}}rep(i, n) nxt[i + n] = nxt[i] + n;rep(i, 3 * n + 1) vec[i][0] = nxt[i];rep(j, 1, 17) rep(i, 3 * n + 1) vec[i][j] = vec[vec[i][j - 1]][j - 1];bool ans = false;rep(i, n) {int now = i;rep(j, 17) {if ((k >> j) & 1) now = vec[now][j];}if (now <= i + n) ans = true;}return ans;};//judge(4);ll ok = -1, ng = 1e15;while (ng - ok > 1) {ll mid = (ng + ok) / 2;(judge(mid) ? ok : ng) = mid;}cout << ok << "\n";return 0;}