Submission #114652

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

shortcut

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

// O(N^3) Solution [[38 pts]]

long long N, C, D[3009][3009], A[3009], B[3009], dp[3009];
long long L[6009], LL[6009], L2[6009];

long long solve_in(int cl, int cr) {
	for (int i = cl; i < cr; i++) L[i - cl] = A[i]; L[cr - cl] = C;
	int M = (cr - cl + 1);
	for (int i = 0; i <= M * 2; i++) LL[i + 1] = LL[i] + L[i % M];
	for (int i = 0; i <= M * 2; i++) L2[i] = LL[i] + B[cl + (i % M)];
	
	long long maxn = 0; for (int i = cl; i <= cr; i++) maxn = max(maxn, B[i]);
	
	int cx = 0; deque<pair<long long, int>> vec;
	for (int i = 0; i < M; i++) {
		while (LL[cx] - LL[i] <= (LL[M] / 2)) {
			while (!vec.empty() && vec[vec.size() - 1].first <= L2[cx]) vec.pop_back();
			vec.push_back(make_pair(L2[cx], cx));
			cx++;
		}
		if (vec.front().second == i) vec.pop_front();
		if (!vec.empty()) maxn = max(maxn, vec.front().first - (LL[i] - B[i]));
	}
	return maxn;
}

long long solve_out(int cl, int cr) {
	long long el = 0, er = 0;
	long long sl = 0; for (int i = cl - 1; i >= 0; i--) { sl += A[i]; el = max(el, sl + B[i]); }
	long long sr = 0; for (int i = cr; i < N - 1; i++) { sr += A[i]; er = max(er, sr + B[i + 1]); }
	long long maxn = 0;
	for (int i = cl; i <= cr; i++) {
		maxn = max(maxn, el + B[i] + min(D[cl][i], D[cl][cr] + C - D[cl][i]));
		maxn = max(maxn, er + B[i] + min(D[cr][i], D[cl][cr] + C - D[cr][i]));
	}
	maxn = max(maxn, el + er + C);
	return maxn;
}

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++) {
			long long V1 = solve_in(i, j);
			long long V2 = solve_out(i, j);
			//cout << "u = " << i << ", v = " << j << ", V1 = " << V1 << ", V2 = " << V2 << ", ans = " << max(V1, V2) << endl;
			ans = min(ans, max(V1, V2));
		}
	}
    return ans;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int solve_in(int, int)':
shortcut.cpp:11:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i = cl; i < cr; i++) L[i - cl] = A[i]; L[cr - cl] = C;
  ^~~
shortcut.cpp:11:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i = cl; i < cr; i++) L[i - cl] = A[i]; L[cr - cl] = C;
                                                  ^

• 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