Submission #739034

#	Time	Username	Problem	Language	Result	Execution time	Memory
739034		Abrar_Al_Samit	Shortcut (IOI16_shortcut)	C++17	23 / 100	1973 ms	308 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"
using namespace std;


const int nax = 100;

long long tab[nax][nax];
int sub[nax];
long long main_line[nax];
int expr;
int n;

long long get(int a, int b, int x, int y) {
    long long ret = main_line[b] - main_line[a];
    ret = min(ret, 
        abs(main_line[x]-main_line[a])+expr+abs(main_line[y]-main_line[b]));
    return ret;
}
long long connect(int a, int b) {
    long long ret = 0;
    for(int i=0; i<n; ++i) {
        for(int j=i+1; j<n; ++j) {
            ret = max(ret, get(i, j, a, b)+sub[i]+sub[j]);
        }
    }
    return ret;
}
long long find_shortcut(int N, vector<int> l, vector<int> d, int c) {
    n = N;
    for(int i=0; i<n; ++i) {
        sub[i] = d[i];
        if(i) main_line[i] = main_line[i-1] + l[i-1];
    }
    expr = c;

    long long ans = 1e18;
    for(int i=0; i<n-1; ++i) {
        for(int j=i+1; j<n; ++j) {
            ans = min(ans, connect(i, j));
        }
    }
    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