Submission #426143

#	Time	Username	Problem	Language	Result	Execution time	Memory
426143		ivan24	Shortcut (IOI16_shortcut)	C++14	23 / 100	2068 ms	348 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;


long long find_shortcut(int n, std::vector<int> len, std::vector<int> d, int c){
    vi pref;
    pref.assign(n,0);
    for (ll i = 1; n > i; i++){
        pref[i] = pref[i-1] + len[i-1];
    }
    ll ans = 1e18;
    for (ll l = 0; n > l; l++){
        for (ll r = l+1; n > r; r++){
            ll diam = 0;
            for (ll i = 0; n > i; i++){
                for (ll j = i+1; n > j; j++){
                    ll cur = pref[j]-pref[i]+d[j]+d[i];
                    cur = min(cur,c+abs(pref[i]-pref[l])+abs(pref[j]-pref[r])+d[j]+d[i]);
                    diam = max(diam,cur);
                    /*
                    if (l <= i && j <= r){
                        cur = min(cur,pref[r]-pref[l]+(pref[i]-pref[l])+(pref[r]-pref[j]));
                    }else if (i < l && j <= r){
                        cur = min(cur,pref[r]-pref[l]+(pref))
                    }else if (l <= i && r < j){

                    }else if (i < l && r < j){

                    }
                    */
                }
            }
            ans = min(ans,diam);
        }
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 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