#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
using namespace std;
typedef long long ll;
struct triple {
int i, l, r, score;
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n;
cin >> n;
vector <int> d(n);
for (int i = 0; i < n; ++i) cin >> d[i];
vector <ll> pref(n + 1);
for (int i = 0; i < n; ++i) {
pref[i + 1] = pref[i] + d[i];
}
vector <triple> gs;
vector <vector <int>> go(n);
vector <vector <int>> who(n);
for (int i = 0; i + 1 < n; ++i) {
int r = 0;
for (int l = 1; l <= i + 1; ++l) {
while (r <= n - i - 1 && pref[i + 1] - pref[i + 1 - l] > pref[i + r + 1] - pref[i + 1]) ++r;
if (pref[i + 1] - pref[i + 1 - l] == pref[i + r + 1] - pref[i + 1]) {
gs.push_back({i, l, r, (int)go[i].size() + 1});
//cout << i + 1 << ' ' << l << ' ' << r << ' ' << go[i].size() + 1 << endl;
int id = (int)gs.size() - 1;
go[i].push_back(id);
who[max(0, i - l - 1)].push_back(id);
}
}
}
vector <int> fen(n);
vector <int> best((int)gs.size());
auto modify = [&] (int id, int val) {
for (; id < n; id |= id + 1) fen[id] = max(fen[id], val);
};
auto get = [&] (int r) {
int res = 0;
for (; r >= 0; r &= r + 1, --r) {
res = max(res, fen[r]);
}
return res;
};
for (int i = 0; i + 1 < n; ++i) {
for (int id : who[i]) {
//cout << "get " << gs[id].i - 1 << ' ' << gs[id].score << ' ' << id << endl;
best[id] = get(gs[id].i - 1) + gs[id].score;
}
for (int id : go[i]) {
//cout << "set " << gs[id].i + gs[id].r << ' ' << best[id] << ' ' << id << endl;
modify(min(n - 1, gs[id].i + gs[id].r + 1), best[id]);
}
}
int ans = 0;
for (auto x : best) ans = max(ans, x);
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
1196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |