Submission #827188

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
827188	2023-08-16T09:42:55 Z	tolbi	Shortcut (IOI16_shortcut)	C++17	0 / 100	0 ms	212 KB

shortcut

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "shortcut.h"
long long find_shortcut(int n, std::vector<int> _p, std::vector<int> d, int c)
{
    vector<ll> pref;
    pref.push_back(0);
    for (int i = 0; i < n-1; i++){
        pref.push_back(_p[i]);
        pref[i+1]+=pref[i];
    }
    function<ll(int,int)> query;
    query = [&](int l, int r)->ll{
        if (l==r) return 0ll;
        if (r<l) swap(l,r);
        return pref[r]-pref[l];
    };
    ll ans = LONG_LONG_MAX;
    function<void(int,int)> dene;
    pair<ll,bool> pr;
    dene = [&](int l, int r){
        ll leftside=0;
        ll rightside=0;
        int indi = 0;
        deque<pair<int,int>> hoaydaaa;
        ll bruh=-1;
        for (int i = 0; i < n; i++){
            if (i){
                while (indi<i){
                    if (query(indi,l)+query(i,r)+c<query(indi,i)){
                        bruh=max(bruh,query(indi,l)+d[indi]);
                        indi++;
                    }
                    else break;
                }
                ll crr = 0;
                while (hoaydaaa.size()>0){
                    ll node = hoaydaaa.back().second;
                    if (indi>node){
                        hoaydaaa.pop_back();
                    }
                    else break;
                }
                if (hoaydaaa.size()>0){
                    crr=max(crr,(ll)d[i]+pref[i]+hoaydaaa.back().first);
                }
                if (bruh!=-1){
                    crr=max(crr,(ll)d[i]+bruh+c+query(i,r));
                }
                if (i>=r){
                    rightside=max(rightside,crr);
                }
                else {
                    leftside=max(leftside,crr);
                }
            }
            while (hoaydaaa.size() && hoaydaaa.front().first<(ll)d[i]-pref[i]){
                hoaydaaa.pop_front();
            }
            hoaydaaa.push_front({(ll)d[i]-pref[i],i});
        }
        pr={max(leftside,rightside),(rightside>leftside)};
    };
    for (int l = 0; l < n; l++){
        int ll = l, rr = n-1;
        while (ll<rr){
            int mid = ll+(rr-ll)/2;
            dene(l,mid);
            ans=min(ans,pr.first);
            if (!pr.second){
                rr=mid;
            }
            else {
                ll=mid+1;
            }
        }
        dene(l,ll);
        ans=min(ans,pr.first);
    }
    for (int i = 0; i < n; ++i)
    {
        ans=max(ans,(ll)d[i]);
    }
    return ans;
}

Subtask #1
0 / 9.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Subtask #2
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Subtask #3
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Subtask #4
0 / 7.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Subtask #5
0 / 33.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Subtask #6
0 / 22.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Subtask #7
0 / 4.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Subtask #8
0 / 3.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	n = 4, 80 is a correct answer
2	Correct	212 KB	n = 9, 110 is a correct answer
3	Correct	212 KB	n = 4, 21 is a correct answer
4	Correct	212 KB	n = 3, 4 is a correct answer
5	Correct	212 KB	n = 2, 62 is a correct answer
6	Correct	212 KB	n = 2, 3 is a correct answer
7	Correct	212 KB	n = 3, 29 is a correct answer
8	Correct	212 KB	n = 2, 3 is a correct answer
9	Correct	212 KB	n = 2, 3 is a correct answer
10	Correct	212 KB	n = 2, 2000000001 is a correct answer
11	Correct	212 KB	n = 2, 3000000000 is a correct answer
12	Correct	212 KB	n = 3, 3000000000 is a correct answer
13	Correct	212 KB	n = 3, 3000000000 is a correct answer
14	Correct	212 KB	n = 4, 3000000001 is a correct answer
15	Correct	212 KB	n = 4, 4000000000 is a correct answer
16	Correct	212 KB	n = 5, 4000000000 is a correct answer
17	Correct	212 KB	n = 10, 1000000343 is a correct answer
18	Correct	212 KB	n = 10, 3189 is a correct answer
19	Incorrect	212 KB	n = 10, incorrect answer: jury 7000000000 vs contestant 8000000000
20	Halted	0 KB	-

Submission #827188

Compilation message