結果
問題 | No.1211 円環はお断り |
ユーザー | toma |
提出日時 | 2020-08-30 16:32:47 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 474 ms / 2,000 ms |
コード長 | 2,931 bytes |
コンパイル時間 | 2,435 ms |
コンパイル使用メモリ | 207,044 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-23 16:23:05 |
合計ジャッジ時間 | 10,839 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 198 ms
5,248 KB |
testcase_14 | AC | 321 ms
5,248 KB |
testcase_15 | AC | 238 ms
5,248 KB |
testcase_16 | AC | 417 ms
5,248 KB |
testcase_17 | AC | 29 ms
5,248 KB |
testcase_18 | AC | 219 ms
5,248 KB |
testcase_19 | AC | 38 ms
5,248 KB |
testcase_20 | AC | 39 ms
5,248 KB |
testcase_21 | AC | 44 ms
5,248 KB |
testcase_22 | AC | 216 ms
5,248 KB |
testcase_23 | AC | 263 ms
5,248 KB |
testcase_24 | AC | 156 ms
5,248 KB |
testcase_25 | AC | 9 ms
5,248 KB |
testcase_26 | AC | 258 ms
5,248 KB |
testcase_27 | AC | 154 ms
5,248 KB |
testcase_28 | AC | 269 ms
5,248 KB |
testcase_29 | AC | 249 ms
5,248 KB |
testcase_30 | AC | 336 ms
5,248 KB |
testcase_31 | AC | 129 ms
5,248 KB |
testcase_32 | AC | 389 ms
5,248 KB |
testcase_33 | AC | 453 ms
5,248 KB |
testcase_34 | AC | 460 ms
5,248 KB |
testcase_35 | AC | 446 ms
5,248 KB |
testcase_36 | AC | 456 ms
5,248 KB |
testcase_37 | AC | 447 ms
5,248 KB |
testcase_38 | AC | 474 ms
5,248 KB |
testcase_39 | AC | 459 ms
5,248 KB |
testcase_40 | AC | 41 ms
5,248 KB |
testcase_41 | AC | 2 ms
5,248 KB |
testcase_42 | AC | 1 ms
5,248 KB |
ソースコード
#include"bits/stdc++.h"using namespace std;#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)#define rep(i,n) REP((i),0,(n))using ll = long long;using pii = pair<int, int>;using pll = pair<ll, ll>;using tp3 = tuple<int, int, int>;using Mat = vector<vector<ll>>;constexpr int INF = 1 << 28;constexpr ll INFL = 1ll << 60;constexpr int dh[4] = { 0,1,0,-1 };constexpr int dw[4] = { -1,0,1,0 };bool isin(const int H, const int W, const int h, const int w) {return 0 <= h && h < H && 0 <= w && w < W;}// ============ template finished ============ll all(const vector<ll>& A) {return accumulate(A.begin(), A.end(), 0ll);}vector<ll> make_acc(vector<ll> A) {const int N = A.size();rep(i, N - 1) {A[i + 1] += A[i];}return A;}ll get(const vector<ll>& acc, ll idx) {return idx == -1 ? 0 : acc[idx];}void update(ll& bestIdx, ll& bestSpan, const ll idx, const ll span) {if (span < bestSpan) {bestIdx = idx;bestSpan = span;}}ll dist(ll from, ll to) {if (from > to) {while (true) {from++;to += from;}}//assert(from <= to);from--;return to - from;}ll need_span(const vector<ll>& acc, const ll idx, const ll val) {const ll N = acc.size();auto itr = lower_bound(acc.begin(), acc.end(), val);if (itr != acc.end()) {return dist(idx, itr - acc.begin());}else {ll need = val - acc.back();itr = lower_bound(acc.begin(), acc.end(), need);return dist(idx, N - 1) + dist(0, itr - acc.begin());}}pll shortest_span(const vector<ll>& acc, const ll M) {const ll N = acc.size();ll bestIdx = -1, bestSpan = INF;rep(left, N) {const ll span = need_span(acc, left, get(acc, left - 1) + M);update(bestIdx, bestSpan, left, span);}return make_pair(bestIdx, bestSpan);}bool canCycle(const vector<ll>& acc, ll idx, const ll K, const ll M) {const ll N = acc.size();ll step = 0;rep(_, K) {ll span = need_span(acc, idx, get(acc, idx - 1) + M);step += span;(idx += span) %= N;}return step <= N;}bool judge(const vector<ll>& A, const ll K, const ll M) {const ll N = A.size();auto acc = make_acc(A);const auto[startIdx, span] = shortest_span(acc, M);assert(span < N / K + 3);for (int i = 0, idx = startIdx; i < span; i++, (++idx) %= N) {if (canCycle(acc, idx, K, M)) {return true;}}return false;}int main(){ll N, K;cin >> N >> K;vector<ll> A(N);rep(i, N)cin >> A[i];if (K == 1) {cout << all(A) << endl;return 0;}ll safe = 0, out = all(A) / K + 1;while (abs(safe - out) > 1) {ll mid = (safe + out) / 2;(judge(A, K, mid) ? safe : out) = mid;}cout << safe << endl;return 0;}