Submission #20752

#	Time	Username	Problem	Language	Result	Execution time	Memory
20752		ainta	Shortcut (IOI16_shortcut)	C++14	71 / 100	1423 ms	2884 KiB

shortcut

#include "shortcut.h"
#include<stdio.h>
#include<algorithm>
#define pll pair<long long, long long>
using namespace std;

int L[3010], C[3010], n, CCC;
long long Res, INF = 1e17, D[3010], P[3010], Deq[6010][2];

pll Do(int m){
    int i, head = 0, tail = 0;
    long long s = 0, ss;
    for(i=0;i<m;i++)s += D[i];
    ss = 0;
    head = 1, tail = 0;
    for(i=0;i<m;i++){
        if(i!=m-1){
            while(head <= tail && Deq[tail][1] >= ss-P[i])tail--;
            tail++;
            Deq[tail][0] = ss, Deq[tail][1] = ss-P[i];
        }
        ss += D[i];
    }
    long long MM = 0, MM2 = 0;
    for(i=0;i<m-1;i++){
        while(head <= tail && (ss - Deq[head][0])*2 > s)head++;
        if(head <= tail){
            MM = max(MM, ss + P[i] - Deq[head][1]);
        }
        while(head <= tail && Deq[tail][1] >= ss-P[i])tail--;
        tail++;
        Deq[tail][0] = ss, Deq[tail][1] = ss-P[i];
        ss += D[i];
    }
    ss = 0;
    for(i=0;i<m-1;i++){
        long long t = s - D[m-1] - ss;
        MM2 = max(MM2, min(t, s-t) + P[i] + P[m-1]);
        ss += D[i];
    }
    return pll(MM,MM2);
}

pll Get(int b, int e){
    long long MM = -1, s = 0, Mn = INF, rr = 0, rr2 = 0;
    int i;
    for(i=b;i>=0;i--){
        rr = max(rr,s+C[i]-Mn);
        MM = max(MM,s+C[i]);
        Mn = min(Mn,s-C[i]);
        if(i)s += L[i-1];
    }
    P[0]=MM;
    D[0]=L[b];
    for(i=b+1;i<e;i++){
        P[i-b] = C[i];
        D[i-b] = L[i];
    }
    MM = -1, s = 0, Mn = INF;
    for(i=e;i<n;i++){
        rr2 = max(rr2,s+C[i]-Mn);
        MM = max(MM,s+C[i]);
        Mn = min(Mn,s-C[i]);
        if(i!=n-1)s += L[i];
    }
    P[e-b] = MM;
    D[e-b] = CCC;
    pll tp = Do(e-b+1);
    rr2 = max(rr2, tp.second);
    rr = max(rr, tp.first);
    return pll(rr,rr2);
}

void Pro(int be){
    int i, B, E, mid, rr = be;
    B = be+1, E = n-1;
    pll tp;
    while(B<=E){
        mid = (B+E)>>1;
        tp = Get(be, mid);
        if(tp.first <= tp.second){
            rr = mid;
            B = mid+1;
        }
        else{
            E = mid-1;
        }
    }
    if(rr != be){
        tp = Get(be, rr);
        Res = min(Res, max(tp.first,tp.second));
    }
    if(rr != n-1){
        tp = Get(be,rr+1);
        Res = min(Res, max(tp.first,tp.second));
    }
}

long long find_shortcut(int N, std::vector<int> l, std::vector<int> d, int c)
{
    n = N;
    if(n>3000)return 0;
    int i, j;
    for(i=0;i<n-1;i++){
        L[i] = l[i];
    }
    for(i=0;i<n;i++){
        C[i] = d[i];
    }
    Res = INF;
    CCC = c;
    for(i=0;i<n;i++){
        Pro(i);
    }
    return Res;
}

Compilation message (stderr)

shortcut.cpp: In function 'void Pro(int)':
shortcut.cpp:75:9: warning: unused variable 'i' [-Wunused-variable]
     int i, B, E, mid, rr = be;
         ^
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:103:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3