This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=5e5+5;
int n;
ll a[N];
map<int,int>dp[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("Partition.INP","r",stdin);
//freopen("Partition.OUT","w",stdout);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
//reverse(a+1,a+n+1);
for(int i=1;i<=n;i++) a[i]+=a[i-1];
dp[1][0]=0;
for(int i=1;i<n;i++)
{
while(dp[i].size()>1) dp[i].erase(dp[i].begin());
for(auto&x:dp[i])
{
dp[i+1][x.fi]=max(dp[i+1][x.fi],x.se);
int v=lower_bound(a+1,a+n+1,2*a[i]-a[x.se])-a;
if(v<=n) dp[v][x.fi+1]=max(dp[v][x.fi+1],i);
}
}
while(dp[n].size()>1) dp[n].erase(dp[n].begin());
auto res=*dp[n].begin();
cout<<res.fi+1;
}
# | 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... |