# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
497932 | vinnipuh01 | Bigger segments (IZhO19_segments) | C++17 | 73 ms | 16060 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* LES GREATEABLES BRO TEAM
**/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");
#define int ll
const int N = 5e5 + 137;
ll a[N], dp[N], last[N], pref[N];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = a[i];
pref[i] += pref[i - 1];
}
dp[1] = 1;
last[1] = 1;
for (int j = 1; j <= n; j++) {
int right = 2 * pref[j] - pref[last[j] - 1];
int lo = j, hi = n, res = -1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (pref[mid] >= right) {
hi = mid;
} else
lo = mid + 1;
}
res = lo;
if (pref[ res ] >= right) {
if (dp[res] <= dp[j] + 1 ) {
dp[res] = dp[j] + 1;
last[res] = j + 1;
}
}
if (dp[j + 1] < dp[j] || ( dp[ j + 1 ] == dp[ j ] && last[ j + 1 ] < last[ j ] )) {
dp[j + 1] = dp[j];
last[j + 1] = last[j];
}
}
cout << dp[n];
}
signed main() {
setIO();
int tt = 1;
if (FLAG) {
cin >> tt;
}
while (tt--) {
solve();
}
return 0;
}
void setIO(const string &f) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen((f + ".in").c_str(), "r")) {
freopen((f + ".in").c_str(), "r", stdin);
freopen((f + ".out").c_str(), "w", stdout);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |