| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 151367 | theboatman | Bigger segments (IZhO19_segments) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define y1 theboatman
#define make_struct(args...) {args}
using namespace std;
typedef long long ll;
const long long INF = 1e18 + 10;
const int inf = 30000 + 10;
const int N = 1e6 + 10;
struct tree {
struct node {
short add;
};
int v, tl, tr;
vector <node> t;
void build(int n) {
v = 1;
tl = 0;
tr = n - 1;
t.assign(n * 4, make_struct(-inf, -inf));
}
void push(int v) {
t[v * 2].add = max(t[v * 2].add, t[v].add);
t[v * 2 + 1].add = max(t[v * 2 + 1].add, t[v].add);
}
void modify(int v, int tl, int tr, int l, int r, int x) {
if (l > r) {
return;
}
if (tl == l && tr == r) {
t[v].add = max(t[v].add, x);
return;
}
int tm = (tl + tr) / 2;
modify(v * 2, tl, tm, l, min(r, tm), x);
modify(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, x);
}
int get(int v, int tl, int tr, int pos) {
if (tl == tr) {
return t[v].add;
}
push(v);
int tm = (tl + tr) / 2;
if (pos <= tm) {
return get(v * 2, tl, tm, pos);
}
else {
return get(v * 2 + 1, tm + 1, tr, pos);
}
}
int get(int pos) {
return get(v, tl, tr, pos);
}
void modify(int l, int r, int x) {
modify(v, tl, tr, l, r, x);
}
};
tree dp[3010];
vector <long long> pref;
long long get(int l, int r) {
long long res = pref[r];
return (l ? res - pref[l - 1] : res);
}
int32_t main() {
cin.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
vector <int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
for(int i = 0; i < n; i++) {
dp[i].build(n);
}
dp[0].modify(0, n - 1, 1);
pref.resize(n);
for(int i = 0; i < n; i++) {
pref[i] = (i ? pref[i - 1] + a[i] : a[i]);
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
int l = j + 1, r = n;
while(l < r) {
int c = (l + r) / 2;
if (get(i, j) > get(j + 1, c)) {
l = c + 1;
}
else {
r = c;
}
}
// l = j + 1;
// while(l < n && get(i, j) > get(j + 1, l)) {
// l++;
// }
//cout << i << " " << j << " " << dp[i].get(j) + 1 << " " << l << " " << n - 1 << "\n";
dp[j + 1].modify(l, n - 1, dp[i].get(j) + 1);
}
}
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
ans = max(ans, dp[i].get(j));
}
}
cout << ans << "\n";
return 0;
}
/*
*/