結果

問題 No.1211 円環はお断り
ユーザー KKT89
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0