Submission #1227546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227546		HossamHero7	Shortcut (IOI16_shortcut)	C++20	31 / 100	2093 ms	2380 KiB

shortcut

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#include "shortcut.h"
// #include "grader.cpp"

long long find_shortcut(int n, std::vector<int> _f, std::vector<int> _d, int _c)
{
    ll c = _c;
    vector<ll> f(n-1) , d(n);
    for(int i=0;i<n-1;i++) f[i] = _f[i];
    for(int i=0;i<n;i++) d[i] = _d[i];
    ll ans = 1e18;
    vector<ll> p(n);
    for(int i=1;i<n;i++){
        p[i] = p[i-1] + f[i-1];
    }
    vector<vector<ll>> f1(n,vector<ll>(n));
    for(int j=0;j<n;j++){
        f1[j][j] = d[j] - p[j];
        for(int i=j+1;i<n;i++){
            f1[j][i] = max(f1[j][i-1],d[i]-p[i]);
        }
    }
    for(int r=0;r<n;r++){
        for(int l=0;l<r;l++){
            ll mx = 0;
            vector<ll> f2(n) , f3(n);
            f2[0] = -p[0] + d[0];
            f3[l] = p[l] + d[l];
            for(int i=1;i<n;i++) f2[i] = max(f2[i-1] , -p[i] + d[i]);
            for(int i=l+1;i<n;i++) f3[i] = max(f3[i-1] , p[i] + d[i]);
            for(int i=1;i<n;i++){
                if(i <= l){
                    mx = max(mx , p[i] + d[i] + f1[0][i-1]);
                }
                else if(i <= r){
                    if(p[l] + p[r] + c < 2 * p[i] && l){
                        mx = max(mx , p[l] + f2[l-1] + c + p[r] - p[i] + d[i]);
                    }
                    else if(l){
                        mx = max(mx , p[i] + d[i] + f1[0][l-1]);
                    }
                    // for(int j=0;j<l;j++){
                    //     ll x = min(p[i] - p[j] , p[l] - p[j] + c + p[r] - p[i]);
                    //     mx = max(mx , x + d[i] + d[j]);
                    // }
                    ll C = -p[l] + c + p[r];
                    int idx = lower_bound(p.begin()+l,p.begin()+min(r,i),(2*p[i]-C+1)/2) - p.begin();
                    if(idx > l) {
                        mx = max(mx , f3[idx-1] + C - p[i] + d[i]);
                    }
                    if(idx < min(r,i)){
                        mx = max(mx , p[i] + d[i] + f1[idx][min(r,i)-1]);
                    }
                    // for(int j=l;j<min(r,i);j++){
                    //     ll x = min(p[i] - p[j] , p[j] - p[l] + c + p[r] - p[i]);
                    //     mx = max(mx , x + d[i] + d[j]);
                    // }
                }
                else {
                    if(l){
                        ll C = p[l] + c - p[r];
                        if(C >= 0) mx = max(mx , p[i] + d[i] + f1[0][l-1]);
                        else mx = max(mx , C + p[i] + d[i] + f2[l-1]);
                    }
                    // for(int j=0;j<l;j++){
                    //     ll x = min(p[i] - p[j] , p[l] - p[j] + c + p[i] - p[r]);
                    //     mx = max(mx , x + d[i] + d[j]);
                    // }
                    for(int j=l;j<min(r,i);j++){
                        ll x = min(p[i] - p[j] , p[j] - p[l] + c + p[i] - p[r]);
                        mx = max(mx , x + d[i] + d[j]);
                    }
                    mx = max(mx , p[i] + d[i] + f1[r][i-1]);
                    // for(int j=r;j<i;j++){
                    //     mx = max(mx , p[i] - p[j] + d[i] + d[j]);
                    // }
                }
            }
            ans = min(ans , mx);
        }
    }
    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: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3