이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIM 500010
using namespace std;
int v[DIM],dp[DIM],poz[DIM];
long long sp[DIM];
int n,i;
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n;
for (i=1;i<=n;i++){
cin>>v[i];
sp[i] = sp[i-1] + v[i];
}
dp[1] = 1;
for (i=2;i<=n;i++){
dp[i] = dp[i-1];
poz[i] = poz[i-1];
int st = 1, dr = i, sol = 0;
while (st <= dr){
int mid = (st+dr)>>1;
if (sp[i] - sp[mid-1] >= sp[mid-1] - sp[poz[mid-1]]){
st = mid+1;
sol = mid;
} else dr = mid-1;
}
if (dp[sol-1] + 1 > dp[i]){
dp[i] = dp[sol-1] + 1;
poz[i] = sol-1;
}
}
cout<<dp[n];
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... |