Submission #1066727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066727		Gromp15	Overtaking (IOI23_overtaking)	C++17	39 / 100	3541 ms	16216 KiB

overtaking

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#include "overtaking.h"
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

int L, N, X, M;
vector<ll> T;
vector<int> W, S;

vector<vector<ar<ll, 2>>> cars;

void init(int _L, int _N, std::vector<long long> _T, std::vector<int> _W, int _X, int _M, std::vector<int> _S)
{
	L = _L;
	N = _N;
	T = _T;
	W = _W;
	X = _X;
	M = _M;
	S = _S;
	W.push_back(X);
	vector<ar<ll, 2>> buses;
	for (int i = 0; i < N; i++) buses.push_back({T[i], i});
	cars.resize(M);
	for (int i = 0; i < M - 1; i++) {
		vector<ar<ll, 3>> ints;
		for (auto [x, y] : buses) {
			ints.push_back({x, x + (ll)W[y] * (S[i+1] - S[i]), y});
		}
		sort(all(ints));
		ll to = 0;
		vector<ar<ll, 2>> buses2;
		vector<ar<ll, 2>> tmp;
		for (auto [l, r, idx] : ints) {
			ckmax(to, r);
			buses2.push_back({to, idx});
			tmp.push_back({l, to});
		}
		swap(buses, buses2);
		cars[i] = tmp;
	}
}

long long arrival_time(long long Y)
{
	ll ans = Y;
	for (int i = 0; i < M - 1; i++) {
		ll orig = ans + (ll)(S[i+1] - S[i]) * X;
		for (auto [l, r] : cars[i]) if (l < ans) ckmax(orig, r);
		ans = orig;
	}
	return ans;
}

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