QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #177289 | #5080. Folding Stick | dj4zo6u_6 | WA | 1ms | 3548kb | C++14 | 743b | 2023-09-12 19:52:01 | 2023-09-12 19:52:01 |
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++){
auto [sd,sj]=*(sol.lower_bound({-s[i],-4e9}));
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: 1ms
memory: 3516kb
input:
4 3 2 2 3
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
5 1 1 1 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
7 1 3 2 3 4 2 2
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3544kb
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: 3508kb
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: 3516kb
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: 3540kb
input:
3 4 2 1
output:
4
result:
ok single line: '4'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3432kb
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: 3464kb
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: 3448kb
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'