| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1286733 | WH8 | Bigger segments (IZhO19_segments) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
signed main(){
int n;cin>>n;
set<pair<int,int>> s;
vector<int> a(n+1, 0), p(n+1, 0);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)p[i]=a[i]+p[i-1];
vector<pair<int,int>> dp(n+1, {0, 1e15});
dp[0]={0, 0};
s.insert({0, 0});
for(int i=1;i<=n;i++){
pair<int,int> from=*prev(s.upper_bound({p[i], 1e15}));
dp[i]={p[i]-p[from.s], dp[from.s].s+1};
pair<int,int> ins={dp[i].f + p[i], i};
if( dp[(*prev(s.upper_bound(ins))).s].s > dp[ins.s].s) continue;
auto it=s.lower_bound(ins);
while(it != s.end() and dp[(*it).s].s <= dp[ins.s].s){
s.erase(it);
it=s.lower_bound(ins);
}
s.insert(ins);
//~ printf("i %lld, endsum %lld, segments %lld\n", i, dp[i].f, dp[i].s);
}
cout<<dp[n].s;
}