QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #177301 | #5080. Folding Stick | dj4zo6u_6 | WA | 0ms | 3876kb | C++14 | 745b | 2023-09-12 20:01:11 | 2023-09-12 20:01:12 |
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;
set<pair<ll,ll>>sol;//-(s[j]+dp[j]),-(s[j]);
sol.insert({0,0});
for(int i=1;i<=n;i++){
int sj=-(*sol.lower_bound({-s[i],-4e9})).second;
dp[i]=s[i]-sj;
sol.insert({-(s[i]+dp[i]),-(s[i])});
}
ll mn=dp[n];
for(int j=n;j>=0;j--){
mn=min<ll>(mn,max<ll>(s[n]-s[j],dp[j]));
}
// for(int i=0;i<=n;i++)cout<<dp[i]<<",\n"[i==n];
cout<<mn<<"\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
4 3 2 2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
5 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
7 1 3 2 3 4 2 2
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: 3836kb
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: 3876kb
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: 3840kb
input:
3 4 2 1
output:
4
result:
ok single line: '4'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
14 7 2 2 2 2 3 4 1 3 5 4 3 1 6
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
35 46 93 64 27 72 55 77 11 17 17 79 83 74 26 32 101 54 112 92 111 77 60 51 19 105 11 68 7 100 49 88 54 106 80 57
output:
366
result:
ok single line: '366'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3624kb
input:
150 87 121 113 120 23 32 107 92 107 40 61 29 100 120 30 62 61 53 103 40 110 56 16 38 12 55 11 71 109 26 60 72 19 121 74 97 11 87 117 32 58 40 104 91 101 118 19 59 79 21 40 111 100 36 105 58 122 61 33 75 66 11 65 97 84 28 90 18 76 68 70 58 112 100 95 28 61 25 24 110 93 117 80 119 105 52 66 66 101 77 ...
output:
852
result:
wrong answer 1st lines differ - expected: '765', found: '852'