Submission #1315712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315712		Luvidi	Shortcut (IOI16_shortcut)	C++20	38 / 100	2095 ms	568 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define fs first
#define sc second

long long find_shortcut(int n, std::vector<int> L, std::vector<int> D, int C)
{   
    ll l[n],d[n];
    for(int i=0;i<n-1;i++)l[i]=L[i];
    l[n-1]=0;
    for(int i=0;i<n;i++)d[i]=D[i];
    ll c=C;

    ll c1[n],c2[n];
    c1[0]=d[0];
    for(int i=1;i<n;i++)c1[i]=max(c1[i-1]+l[i-1],d[i]);
    c2[n-1]=d[n-1];
    for(int i=n-2;i>-1;i--)c2[i]=max(c2[i+1]+l[i],d[i]);
    ll m1[n],m2[n];
    m1[0]=d[0];
    for(int i=1;i<n;i++)m1[i]=max(m1[i-1],d[i]+l[i-1]+c1[i-1]);
    m2[n-1]=d[n-1];
    for(int i=n-2;i>-1;i--)m2[i]=max(m2[i+1],d[i]+l[i]+c2[i+1]);

    ll ans=1e18;
    for(int x=0;x<n;x++){
        for(int y=x+1;y<n;y++){
            ll dx=d[x],dy=d[y],ly=l[y];
            d[x]=c1[x];
            d[y]=c2[y];
            l[y]=c;

            ll s=0;
            for(int i=x;i<=y;i++)s+=l[i];
            s/=2;
            deque<pll> dq;
            // ms.insert(d[x]);
            dq.pb({x,d[x]});
            ll mx=max(m1[x],m2[y]);
            for(ll i=x,j=x,pi=0,pj=0;i<=y;i++){
                while(pj+l[j]-pi<=s){
                    pj+=l[j];
                    j++;
                    if(j>y)j=x;
                    ll t=pj+d[j];
                    while(!dq.empty()&&dq.back().sc<t)dq.pop_back();
                    dq.pb({j,t});
                }
                if(dq.front().fs==i)dq.pop_front();
                if(!dq.empty()){
                    mx=max(mx,dq[0].sc-pi+d[i]);
                }
                pi+=l[i];
            }
            ans=min(ans,mx);
            d[x]=dx;
            d[y]=dy;
            l[y]=ly;
        }
    }

    return ans;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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