QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#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

你现在查看的是最新测评结果

[2023-09-12 20:01:12]
评测

测评结果：WA
用时：0ms
内存：3876kb

查看

[2023-09-12 20:01:11]
提交

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";
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3580kb

input:

4
3 2 2 3

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3636kb

input:

5
1 1 1 1 1

output:

result:

ok single line: '1'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

7
1 3 2 3 4 2 2

output:

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:

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:

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:

result:

ok single line: '14'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

3
4 2 1

output:

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:

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:

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:

result:

wrong answer 1st lines differ - expected: '765', found: '852'