이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int a[3001];
ll p[3001];
set<pair<ll,ll> > s[3001];
ll d[3001][3001];
int n;
int main(){
cin>>n;
for(int k=1;k<=n;k++){
cin>>a[k];
p[k]=p[k-1]+a[k];
}
d[0][0]=0;
s[0].insert({0,0});
set<pair<ll,ll> >::iterator it;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
it=s[j-1].lower_bound({p[i]+1,0});
if(it==s[j-1].begin()){
d[i][j]=1e18;
continue;
}
it--;
int ind=(*it).ss;
d[i][j]=p[i]-p[ind];
ll v=d[i][j]+p[i];
while(!s[j].empty()&&(*s[j].rbegin()).ff>=v){
s[j].erase(*s[j].rbegin());
}
s[j].insert({v,i});
}
}
for(int j=n;j>=1;j--){
if(d[n][j]!=1e18){
cout<<j;
return 0;
}
}
return 0;
}
# | 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... |