Submission #1020846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020846		vjudge1	Shortcut (IOI16_shortcut)	C++17	31 / 100	2015 ms	600 KiB

shortcut

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

#define ll long long
// #define int ll
#define pii pair<int,int>
#define F first
#define S second
#define sz(s) (int)s.size()
#define in insert
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))

using namespace std;

const int MAX=2e5+10;
const ll inf=1e18;

int n;
ll c;
ll pin[MAX];
ll pin1[MAX];

ll get(int l,int r,vector<int> &d){
    ll ans=0;
    // cout<<l<<" "<<r<<"\n";
    {
        ll mx1=-inf;
        for(int i=0;i<=l;i++){
            ans=max(ans,pin[i]+d[i]+mx1);
            // cout<<pin[i]+d[i]+mx1<<"\n";
            mx1=max(mx1,d[i]-pin[i]);
        }
    }
    {
        ll mx1=-inf;
        for(int i=0;i<l;i++)mx1=max(mx1,pin[l]-pin[i]+d[i]);
        for(int i=l;i<=r;i++){
            // cout<<mx1+min(pin[i]-pin[l],pin[r]-pin[i]+c)+d[i]<<"\n";
            ans=max(ans,mx1+min(pin[i]-pin[l],pin[r]-pin[i]+c)+d[i]);
        }
    }
    {
        ll mx1=-inf;
        for(int i=0;i<=l;i++){
            mx1=max(mx1,pin[l]-pin[i]+d[i]);
        }
        for(int i=r;i<n;i++){
            // cout<<pin[i]-pin[r]+min(c,pin[r]-pin[l])+mx1+d[i]<<"\n";
            ans=max(ans,pin[i]-pin[r]+min(c,pin[r]-pin[l])+mx1+d[i]);
        }
    }
    // cout<<"!! "<<ans<<"\n";
    return ans;
}

ll calc(int l,int r,vector<int> &d){
    ll ans=get(l,r,d);
    reverse(all(d));
    for(int i=0;i<n;i++)swap(pin[i],pin1[i]);
    ans=max(ans,get(n-r-1,n-l-1,d));
    reverse(all(d));
    for(int i=0;i<n;i++)swap(pin[i],pin1[i]);
    return ans;
}

ll calcmid(int l,int r,vector<int> &d){
    ll ans=0;
    for(int i=l;i<=r;i++){
        for(int j=i+1;j<=r;j++){
            ll dist=pin[j]-pin[i];
            ans=max(ans,min(dist,pin[r]-pin[l]+c-dist)+d[i]+d[j]);
        }
    }
    return ans;
}

long long find_shortcut(int N, vector<int> l, vector<int> d, int C){
    n=N;
    c=C;
    ll ans=inf;
    for(int i=1;i<n;i++){
        pin[i]=pin[i-1]+l[i-1];
    }

    for(int i=1;i<n;i++){
        pin1[i]=pin1[i-1]+l[n-1-i];
    }
    for(int i=0;i<n;i++){
        ll mid=-inf,mid1=-inf;
        for(int j=i+1;j<n;j++){
            ll x=calc(i,j,d);
            ans=min(ans,max(x,calcmid(i,j,d)));
            // cout<<x<<" "<<calcmid(i,j,d)<<"\n";
        }
    }
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:91:12: warning: unused variable 'mid' [-Wunused-variable]
   91 |         ll mid=-inf,mid1=-inf;
      |            ^~~
shortcut.cpp:91:21: warning: unused variable 'mid1' [-Wunused-variable]
   91 |         ll mid=-inf,mid1=-inf;
      |                     ^~~~

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