QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #177268 | #5080. Folding Stick | dj4zo6u_6 | WA | 1ms | 3552kb | C++14 | 662b | 2023-09-12 19:31:06 | 2023-09-12 19:31:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve();
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
solve();
}
void solve(){
int n;
cin>>n;
vector<ll>a(n+5,0),dp(n+5,2e9),s(n+5,0);
for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
dp[0]=0;
for(int i=1;i<=n;i++){
int l=0;
for(int r=i+1,m;l+1<r;){
m=(l+r)/2;
if(dp[m]+s[m]<=s[i])l=m;
else r=m;
}
dp[i]=s[i]-s[l];
}
ll mn=dp[n];
for(int j=n;j>=0;j--){
mn=min<ll>(mn,max<ll>(s[n]-s[j],dp[j]));
}
cout<<mn<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3456kb
input:
4 3 2 2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
5 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
7 1 3 2 3 4 2 2
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
9 5 6 3 4 8 8 2 2 5
output:
9
result:
ok single line: '9'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
10 5 6 3 4 8 6 2 1 8 5
output:
9
result:
ok single line: '9'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
10 5 8 1 2 6 8 4 3 6 5
output:
14
result:
ok single line: '14'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
3 4 2 1
output:
4
result:
ok single line: '4'
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 3432kb
input:
14 7 2 2 2 2 3 4 1 3 5 4 3 1 6
output:
12
result:
wrong answer 1st lines differ - expected: '8', found: '12'