Submission #980811

#	Time	Username	Problem	Language	Result	Execution time	Memory
980811		qilby	Overtaking (IOI23_overtaking)	C++17	0 / 100	4 ms	8280 KiB

overtaking

#include <bits/stdc++.h>

#include "overtaking.h"

using namespace std;
using ll = long long;

const int N = 1009;

ll f[N][N];
int L, n, x, m, q;
vector < ll > t(N);
vector < int > w(N), s(N);
vector < vector < ll > > e(N, vector < ll > (N));

void init(int l_, int n_, vector < ll > t_, vector < int > w_, int x_, int m_, vector < int > s_) {
	L = l_, n = n_, m = m_, x = x_;

	for (int i = 0; i < n; i++) t[i] = t_[i], w[i] = w_[i], s[i] = s_[i];

	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			if (!j) e[j][i] = t[i];
			else e[j][i] = e[j - 1][i] + w[i] * (s[j] - s[j - 1]);
		}

		if (j) {
			for (int i = 0; i < n; i++) {
				for (int k = 0; k < n; k++) if (e[j - 1][k] < e[j - 1][i]) e[j][i] = max(e[j][i], e[j][k]);
			}
		}
	}

	for (int j = m - 1; j >= 0; j--) {
		for (int i = 0; i < n; i++) {
			if (j == m - 1) f[j][i] = e[j][i];
			else {
				int mnl = (int)1e9, opt = -1;

				for (int k = 0; k < n; k++) {
					if (e[j][k] >= e[j][i]) continue;

					int l = j + 1, r = m - 1;

					while (l < r) {
						int mid = (l + r) >> 1;
						if (e[mid][k] >= e[j][i] + x * (s[mid] - s[j])) r = mid;
						else l = mid + 1;
					}

					if (e[l][k] >= e[j][i] + x * (s[l] - s[j]) && (l < mnl ||
						(l == mnl && e[l][k] > e[l][opt]))) {
						mnl = l, opt = k;
					}
				}

				if (mnl < (int)1e9) f[j][i] = f[mnl][opt];
				else f[j][i] = e[j][i] + x * (L - s[j]);
			}
		}
	}
}

ll arrival_time(ll y) {
	int mnl = (int)1e9, opt = -1, j = 0;

	for (int k = 0; k < n; k++) {
		if (e[j][k] >= y) continue;

		int l = j + 1, r = m - 1;

		while (l < r) {
			int mid = (l + r) >> 1;
			if (e[mid][k] >= y + x * (s[mid] - s[j])) r = mid;
			else l = mid + 1;
		}

		if (e[l][k] >= y + x * (s[l] - s[j]) && (l < mnl ||
			(l == mnl && e[l][k] > e[l][opt]))) {
			mnl = l, opt = k;
		}
	}

	if (mnl < (int)1e9) return f[mnl][opt];

	return x * L + y;
}

/*int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> L >> n >> x >> m >> q;

	for (int i = 0; i < n; i++) cin >> t[i];

	for (int i = 0; i < n; i++) cin >> w[i];

	for (int i = 0; i < m; i++) cin >> s[i];

	init(L, n, t, w, x, m, s);

	cout << "\n";

	while (q--) {
		ll y;
		cin >> y;
		cout << arrival_time(y) << "\n";
	}
}*/

/*
10 1 5 5 10
0
6
0 2 8 9 10
9
2
4
5
0
1
2
3
10
20
*/

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35