Submission #1283253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283253		KindaGoodGames	Shortcut (IOI16_shortcut)	C++20	31 / 100	2093 ms	436 KiB

shortcut

#pragma GCC optimize("O3,unroll-loops,Ofast")
#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long

int INF = numeric_limits<int>::max()/2; 
int calc(int a, int b, int32_t n, vector<int>& pn, vector<int>& sn, std::vector<int32_t>& d, int32_t c){
    int ma = 0; 
    // LL
    for(int i = 0; i <= a; i++){
        for(int j = i+1; j <= a; j++){
            ma = max(ma, pn[j]-pn[i]+d[i]+d[j]);
        }
    } 
    // MM
    for(int i = a; i <=b; i++){
        for(int j = i+1; j <= b; j++){
            ma = max(ma, min(pn[j]-pn[i],pn[i]-pn[a]+sn[j]-sn[b]+c)+d[i]+d[j]);
        }
    }
    // RR
    for(int i = b; i <=n-1; i++){
        for(int j = i+1; j <= n-1; j++){
            ma = max(ma, pn[j]-pn[i]+d[i]+d[j]);
        }
    }
    
    // LR
    for(int i = 0; i <=a; i++){
        for(int j = b; j <= n-1; j++){
            ma = max(ma, pn[a]-pn[i]+sn[b]-sn[j]+d[i]+d[j]+c);
        }
    }  

    // LM
    for(int i = 0; i <=a; i++){
        for(int j = max(a,i+1); j <= b; j++){
            ma = max(ma, pn[a]-pn[i]+d[i]+min(sn[j]-sn[b]+c,pn[j]-pn[a])+d[j]);
        }
    }  
    
    // MR
    for(int i = a; i <=b; i++){
        for(int j = max(b,i+1); j <= n-1; j++){
            ma = max(ma, sn[b]-sn[j]+d[i]+min(sn[i]-sn[b],pn[i]-pn[a]+c)+d[j]);
        }
    }  
     
    return ma;
}

long long find_shortcut(int32_t n, std::vector<int32_t> l, std::vector<int32_t> d, int32_t c)
{
    vector<int> pref(n);
    for(int i = 1; i < n; i++){
        pref[i] = pref[i-1]+l[i-1];
    }
    vector<int> suff(n);
    for(int i = n-2; i >= 0; i--){
        suff[i] = suff[i+1]+l[i];
    } 
    int mi = calc(0,1,n,pref,suff,d,l[0]);
    
    for(int a = 0; a < n; a++){
        for(int b = a+1; b < n; b++){ 
            int v = calc(a,b,n,pref,suff,d,c);
            mi = min(mi,v);
        }
    }
    return mi;
}

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