Submission #879814

#	Time	Username	Problem	Language	Result	Execution time	Memory
879814		SanguineChameleon	Overtaking (IOI23_overtaking)	C++17	39 / 100	3554 ms	18460 KiB

overtaking

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

long long off = 0;
vector<pair<long long, long long>> queries;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
	vector<pair<long long, int>> cur_T;
	for (int i = 0; i < N; i++) {
		if (W[i] > X) {
			cur_T.emplace_back(T[i], W[i]);
		}
	}
	for (int i = 0; i < M - 1; i++) {
		sort(cur_T.begin(), cur_T.end());
		vector<pair<long long, int>> nxt_T(cur_T.size());
		int start = 0;
		long long mx = 0;
		int dist = S[i + 1] - S[i];
		for (int j = 0; j < (int)cur_T.size(); j++) {
			if (j > 0 && cur_T[j].first != cur_T[j - 1].first) {
				for (int k = start; k < j; k++) {
					mx = max(mx, nxt_T[k].first);
				}
				start = j;
			}
			nxt_T[j] = {max(mx, cur_T[j].first + 1LL * cur_T[j].second * dist), cur_T[j].second};
		}
		for (int j = (int)cur_T.size() - 1; j >= 0; j--) {
			queries.emplace_back(cur_T[j].first - off, nxt_T[j].first - off - 1LL * X * dist);
		}
		off += 1LL * X * dist;
		cur_T.swap(nxt_T);
	}
}

long long arrival_time(long long Y) {
	long long res = Y;
	for (auto [A, B]: queries) {
		if (res > A) {
			res = max(res, B);
		}
	}
	res += off;
	return res;
}

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