結果
問題 | No.1211 円環はお断り |
ユーザー |
|
提出日時 | 2024-09-07 23:22:52 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 2,005 bytes |
コンパイル時間 | 2,934 ms |
コンパイル使用メモリ | 219,600 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-07 23:22:58 |
合計ジャッジ時間 | 5,334 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef unsigned long long int ull;mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ll myRand(ll B) { return (ull)rng() % B; }int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int n, k;cin >> n >> k;vector<ll> r_sum(n + 1);vector<ll> a(n);for (int i = 0; i < n; i++) {cin >> a[i];r_sum[i + 1] = r_sum[i] + a[i];}ll L = 0, R = 1e18;auto solve = [&](ll x) -> bool {int cnt = 0;ll sum = 0;for (int i = 0; i < n; i++) {sum += a[i];if (sum >= x) {sum = 0;cnt++;}}if (cnt <= k - 2) return false;if (cnt >= k) return true;vector<int> left(n, -1);sum = 0;int r = 0;for (int l = 0; l < n; l++) {while (r < n and sum < x) {sum += a[r];r++;}if (sum >= x) {left[l] = r;} else break;sum -= a[l];}vector<pair<int, int>> v(n + 1);for (int i = 0; i <= n; i++) {v[i] = {0, i};}for (int i = n - 1; i >= 0; i--) {if (left[i] == -1) continue;int nxt = left[i];v[i] = v[nxt];v[i].first++;}ll pre_sum = 0;ll suf_sum = 0;for (int i = 0; i < n; i++) {if (v[i].first != k - 1) break;int ed = v[i].second;// [ed,n)suf_sum = r_sum[n] - r_sum[ed];if (pre_sum + suf_sum >= x) return true;pre_sum += a[i];}return false;};while (R - L > 1) {ll mid = (L + R) / 2;if (solve(mid)) {L = mid;} else {R = mid;}}cout << L << endl;}