Submission #1221733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221733		AmirAli_H1	Shortcut (IOI16_shortcut)	C++17	38 / 100	572 ms	840 KiB

shortcut

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1500 + 4;
const ll oo = 1e18 + 4;
const int maxlg = 12;

int n; ll w;
ll A[maxn], D[maxn], A1[maxn], A2[maxn];
ll valx[maxn], valD[maxn]; ll M1[maxn][maxlg], M2[maxn][maxlg];

ll get_max1(int l, int r) {
	if (r - l <= 0) return -oo;
	int j = __lg(r - l);
	return max(M1[l][j], M1[r - (1 << j)][j]);
}

ll get_max2(int l, int r) {
	if (r - l <= 0) return -oo;
	int j = __lg(r - l);
	return max(M2[l][j], M2[r - (1 << j)][j]);
}

ll cal1(int i, int x, int l, int r) {
	ll res = -oo;
	if (x == 0) return res;
	if (i - x >= l) {
		res = max(res, A[i] + (D[i] + get_max2(i - x, i)));
	}
	else {
		res = max(res, A[i] + (D[i] + get_max2(l, i))); x -= (i - l);
		res = max(res, A[i] + (D[i] - D[l]) + w + (D[r] + get_max2(r - x + 1, r + 1)));
	}
	return res;
}

ll cal2(int i, int x, int l, int r) {
	ll res = -oo;
	if (x == 0) return res;
	if (i + x <= r) {
		res = max(res, A[i] + (get_max1(i + 1, i + x + 1) - D[i]));
	}
	else {
		res = max(res, A[i] + (get_max1(i + 1, r + 1) - D[i])); x -= (r - i);
		res = max(res, A[i] + (D[r] - D[i]) + w + (get_max1(l, l + x) - D[l]));
	}
	return res;
}

ll calD(int m, int i, int j) {
	if (i == j) return -oo;
	return min(valD[j] - valD[i], valD[i] + (valD[m - 1] - valD[j]) + w) + valx[i] + valx[j];
}

ll calR(int m, int l, int r) {
	ll res = 0;
	for (int i = 0; i < m; i++) {
		res = max(res, max(max(calD(m, 0, i), calD(m, i, m - 1)), valx[i]));
	}
	int j = 0;
	for (int i = m; i < 3 * m; i++, j++) {
		if (j >= m) j -= m;
		valx[i] = valx[j];
		valD[i] = valD[(i - j) - 1] + w + valD[j];
	}
	j = 0;
	for (int i = m; i < 2 * m; i++) {
		j = max(j, i - m + 1);
		while ((valD[i] - valD[j]) > (valD[j + m] - valD[i])) j++;
		res = max(res, cal1(l + (i - m), (i - j), l, r));
		res = max(res, cal2(l + (i - m), (j + m) - (i + 1), l, r));
	}
	return res;
}

ll calx(int l, int r) {
	if (l == r) return max(A1[n - 1], A2[0]);
	ll res = max(A1[l], A2[r]);
	for (int i = l; i <= r; i++) {
		valx[i - l] = A[i]; valD[i - l] = D[i] - D[l];
	}
	int m = (r - l + 1);
	for (int i = 0; i < l; i++) valx[0] = max(valx[0], A[i] + (D[l] - D[i]));
	for (int i = r + 1; i < n; i++) valx[m - 1] = max(valx[m - 1], A[i] + (D[i] - D[r]));
	res = max(res, calR(m, l, r));
	return res;
}

ll find_shortcut(int nx, vector<int> lx, vector<int> dx, int cx) {
	n = nx; w = cx; D[0] = 0;
	for (int i = 0; i < n; i++) A[i] = dx[i];
	for (int i = 1; i < n; i++) D[i] = D[i - 1] + lx[i - 1];
	for (int i = n - 1; i >= 0; i--) {
		M1[i][0] = A[i] + D[i];
		M2[i][0] = A[i] - D[i];
		for (int j = 1; j < maxlg; j++) {
			if (i + (1 << j) - 1 >= n) break;
			M1[i][j] = max(M1[i][j - 1], M1[i + (1 << (j - 1))][j - 1]);
			M2[i][j] = max(M2[i][j - 1], M2[i + (1 << (j - 1))][j - 1]);
		}
	}
	ll mx = -oo;
	for (int i = 0; i < n; i++) {
		A1[i] = max(A[i], (A[i] + D[i]) + mx);
		if (i - 1 >= 0) A1[i] = max(A1[i], A1[i - 1]);
		mx = max(mx, A[i] - D[i]);
	}
	mx = -oo;
	for (int i = n - 1; i >= 0; i--) {
		A2[i] = max(A[i], (A[i] - D[i]) + mx);
		if (i + 1 < n) A2[i] = max(A2[i], A2[i + 1]);
		mx = max(mx, A[i] + D[i]);
	}
	ll ans = oo;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			ans = min(ans, calx(i, j));
		}
	}
	return ans;
}

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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