Submission #1311869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311869		settop	Shortcut (IOI16_shortcut)	C++20	0 / 100	1 ms	348 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>

using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll long long
#define fall(i,a,b) for(int i=a;i<=b;i++)
#define rfall(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const ll inf=1e16;
typedef pair<ll,ll> pii;

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){
    vector<ll> pref(n),suf(n),dist(n),rdist(n),adicionou(n);

    pref[0]=d[0];
    fall(i,1,n-1) pref[i]=max(1ll*d[i],pref[i-1]+1ll*l[i-1]);

    suf[n-1]=d[n-1];
    rfall(i,n-2,0) suf[i]=max(suf[i+1]+1ll*l[i],d[i]*1ll);

    dist[0]=d[0];
    fall(i,1,n-1) dist[i]=max(dist[i-1],pref[i-1]+1ll*l[i-1]+1ll*d[i]);

    rdist[n-1]=d[n-1];
    rfall(i,n-2,0) rdist[i]=max(rdist[i],suf[i+1]+1ll*l[i]+1ll*d[i]);

    auto calc=[&](int a,int r){
        ll gap=0,dr=d[r],dl=d[a];
        fall(i,a,r-1) gap+=l[i];

        ll p=r,dc=0,cur=0,mx=0;
        multiset<ll> st; st.insert(d[r]); adicionou[r]=d[r];

        //cout<<r<<" "<<adicionou[r]<<"\n";

        rfall(i,r-1,a){ //acha o par mais distante entre as bordas da bridge       
            cur+=l[i];
            dc-=l[i];

            while(p>i){
                ll x=adicionou[p]+cur;
                if(2*x>gap+c+2ll*d[p]){
                    st.erase(st.find(adicionou[p]));
                    dc=max(dc,gap-x+1ll*c+2ll*d[p]);
                    p--;
                }
                else break;
            }
            
            ll x=adicionou[r]+cur;
            dr=max(dr,1ll*d[i]+min(cur,c+gap-cur));

            if(i==a) dl=max(dl,dc);
            if(i==a && !st.empty()) dl=max(dl,*st.rbegin()+cur);

            mx=max(mx,dc+1ll*d[i]);
            if(!st.empty()) mx=max(mx,*st.rbegin()+cur+d[i]);

            st.insert(1ll*d[i]-cur);
            adicionou[i]=1ll*d[i]-cur;
        }

        if(a) mx=max(mx,dist[a-1]);
        if(r!=n-1) mx=max(mx,rdist[r+1]);

        gap=min(gap,1ll*c);

        ll d1=0,d2=0;
        if(a) d1=pref[a-1]+l[a-1];
        if(r!=n-1) d2=suf[r+1]+l[r];

        mx=max({mx,d1+dl,d2+dr,d1+gap+d2});

        return mx;
    };

    ll ans=inf;

    fall(i,0,n-1)
        fall(j,i+1,n-1){
            ans=min(ans,calc(i,j));
            //if(calc(i,j)==100) cout<<i<<" "<<j<<"\n";
        }
                       
    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: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3