Submission #426241

#	Time	Username	Problem	Language	Result	Execution time	Memory
426241		InternetPerson10	Shortcut (IOI16_shortcut)	C++17	23 / 100	2091 ms	1740 KiB

shortcut

#include "shortcut.h"
typedef long long ll;

using namespace std;

ll arr[1001][1001];

long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    ll best = 999999999999999999;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if(j - i == 1) arr[i][j] = arr[j][i] = l[i];
            else arr[i][j] = arr[j][i] = arr[i][j-1] + l[j-1];
        }
    }
    for(int le = 0; le < n; le++) {
        for(int ri = le+1; ri < n; ri++) {
            ll biggest = -1;
            for(int i = 0; i < n; i++) {
                for(int j = i+1; j < n; j++) {
                    biggest = max(biggest, d[i] + d[j] + min(arr[i][j], arr[i][le] + c + arr[ri][j]));
                }
            }
            best = min(biggest, best);
        }
    }
    return best;
}

• 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