Submission #136836

#	Time	Username	Problem	Language	Result	Execution time	Memory
136836		antimirage	Shortcut (IOI16_shortcut)	C++14	38 / 100	525 ms	8696 KiB

shortcut

#include "shortcut.h"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 505;

int a[N], d[N], n;

long long suf[N], ans = 1e18, pos[N], inf = 1e18, calc[N][N], mx[N][N];

long long find_shortcut(int N, vector<int> qwe, vector<int> asd, int c) { n = N;
	for (int i = 0; i < n - 1; i++) {
		a[i] = asd[i];
		d[i] = qwe[i];
		if (i > 0) {
			pos[i] = pos[i - 1] + qwe[i - 1];
		}
	}
	pos[n - 1] = pos[n - 2] + qwe[n - 2];
	a[n - 1] = asd[n - 1];
	for (int x = 0; x < n; x++) {
		mx[x][x] = pos[x] + a[x];
		mx[x + 1][x] = -inf;
		for (int y = x + 1; y < n; y++) {
			mx[x][y] = max(mx[x][y - 1], pos[y] + a[y]);
		}
	}
	for (int x = 0; x < n; x++) {
		for (int y = x + 1; y < n; y++) {
			for (int i = y; i >= x; i--) {
				suf[i] = max( (i == y ? 0 : suf[i + 1]), pos[y] - pos[i] + a[i]);
			}
			int j = x + 1;
			for (int i = x; i < y; i++) {
				while (j <= y && pos[j] - pos[i] < pos[i] - pos[x] + pos[y] - pos[j] + c)
					j++;
					
				if (j > y)
					calc[x][y] = max(calc[x][y], mx[i + 1][y] - pos[i] + a[i]);
				else
					calc[x][y] = max(calc[x][y], max(mx[i + 1][j - 1] - pos[i] + a[i], c + suf[j] + a[i] + pos[i] - pos[x]));
			}
		}
	}
	for (int x = 0; x < n; x++) {
		for (int y = x + 1; y < n; y++) {
			long long mx1 = 0, mx2 = 0, res = calc[x][y];
			for (int i = 0; i <= x; i++) {
				mx1 = max(mx1, pos[x] - pos[i] + a[i]);
			}
			for (int i = y; i < n; i++) {
				mx2 = max(mx2, pos[i] - pos[y] + a[i]);
			}
			res = max(res, mx1 + mx2 + min(c * 1ll, pos[y] - pos[x]));
			
			for (int i = y - 1; i >= x; i--) {
				res = max(res, min(c + pos[i] - pos[x], pos[y] - pos[i]) + mx2 + a[i]);
			}
			for (int i = x + 1; i <= y; i++) {
				res = max(res, min(c + pos[y] - pos[i], pos[i] - pos[x]) + mx1 + a[i]);
			}
			for (int i = 0; i < x; i++) {
				res = max(res, mx[i + 1][x] - pos[i] + a[i]);
			}
			for (int i = y; i < n - 1; i++) {
				res = max(res, mx[i + 1][n - 1] - pos[i] + a[i]);
			}
			ans = min(ans, res);
		}
	}
	return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3