#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
using namespace std;
#define int long long
int log_ = 10;
int inf = 1000000000000000000;
int mod = 998244353;
signed main()
{
ios_base::sync_with_stdio();
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector <int> a(n);
vector <int> pref(n);
vector <int> dp(n);
vector <int> col(n);
int pr = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
pr += a[i];
pref[i] = pr;
dp[i] = pref[i];
col[i] = 1;
}
pref.push_back(inf);
vector <int> syf(n , -1);
vector <int> syf_col(n , 1);
int ans = 0;
for (int i = 0; i < n; i++)
{
int x = pref[i];
if (i > 0)
{
if (syf[i - 1] == syf[i])
syf_col[i] = max(syf_col[i - 1], syf_col[i]);
if (syf[i - 1] > syf[i])
syf[i] = syf[i - 1];
}
if (syf[i] != -1)
dp[i] = pref[i] - pref[syf[i]];
else
dp[i] = pref[i];
col[i] = syf_col[i];
ans = max(ans, col[i]);
int ind = lower_bound(pref.begin(), pref.end(), x + dp[i]) - pref.begin();
if (ind == n)
continue;
syf[ind] = i;
syf_col[ind] = col[i]+1;
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |