Submission #114647

#	Time	Username	Problem	Language	Result	Execution time	Memory
114647		E869120	Shortcut (IOI16_shortcut)	C++14	0 / 100	3 ms	384 KiB

shortcut

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

long long N, C, D[509][509], A[509], B[509], dp[509];

long long solve(int cl, int cr) {
	for (int i = 0; i < N; i++) dp[i] = D[0][i];
	if (dp[cl] > dp[cr] + C) { dp[cl] = dp[cr] + C; }
	if (dp[cr] > dp[cl] + C) { dp[cr] = dp[cl] + C; }
	for (int i = 0; i < N - 1; i++) dp[i + 1] = min(dp[i + 1], dp[i] + D[i][i + 1]);
	for (int i = N - 2; i >= 0; i--) dp[i] = min(dp[i], dp[i + 1] + D[i][i + 1]);
	pair<long long, int> m1 = make_pair(-1LL, -1);
	for (int i = 0; i < N; i++) m1 = max(m1, make_pair(dp[i] + B[i], i));
	
	int root = m1.second;
	for (int i = 0; i < N; i++) dp[i] = D[root][i];
	if (dp[cl] > dp[cr] + C) { dp[cl] = dp[cr] + C; }
	if (dp[cr] > dp[cl] + C) { dp[cr] = dp[cl] + C; }
	for (int i = 0; i < N - 1; i++) dp[i + 1] = min(dp[i + 1], dp[i] + D[i][i + 1]);
	for (int i = N - 2; i >= 0; i--) dp[i] = min(dp[i], dp[i + 1] + D[i][i + 1]);
	pair<long long, int> m2 = make_pair(B[root], root);
	for (int i = 0; i < N; i++) { if (i == root) continue; m2 = max(m2, make_pair(dp[i] + B[i] + B[root], i)); }
	
	return m2.first;
}

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) {
	N = n; C = c;
	for (int i = 0; i < N; i++) { if (i < N - 1) A[i] = l[i]; B[i] = d[i]; }
	for (int i = 0; i < N; i++) {
		long long S = 0;
		for (int j = i + 1; j < N; j++) {
			S += 1LL * l[j - 1];
			D[i][j] = S; D[j][i] = S;
		}
	}
	
	long long ans = (1LL << 60);
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) ans = min(ans, solve(i, j));
	}
    return ans;
}

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