Submission #857437

#	Time	Username	Problem	Language	Result	Execution time	Memory
857437		mychecksedad	Overtaking (IOI23_overtaking)	C++17	65 / 100	3524 ms	26208 KiB

overtaking

#include <overtaking.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define MOD (1000000000)+7;
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e3+100;

int L, n, m;
vector<int> W, S;
vector<ll> T;
vector<array<ll, 2>> pref[N];
ll X, dp[N][N];

void init(int l, int _n, vector<ll> t, vector<int> w, int x, int _m, vector<int> s){
	W = w;
	S = s;
	T = t;
	S = s;
	n = _n;
	m = _m;
	X = x;

	for(int i = 0; i < n; ++i) dp[i][0] = T[i];
	for(int j = 1; j < m; ++j){
		vector<array<ll, 2>> b;
		for(int i = 0; i < n; ++i) b.pb({dp[i][j - 1], i});
		sort(all(b));
		ll cur = 0, curlast = 0;
		for(int i = 0; i < n; ++i){
			int v = b[i][1];
			// cout << v << ' ' << j << ' ' << dp[v][j - 1] << '\n';
			if(i > 0 && dp[b[i - 1][1]][j - 1] < dp[v][j - 1]) curlast = cur;
			cur = max(cur, dp[v][j - 1] + (ll)W[v] * (S[j] - S[j - 1]));
			dp[v][j] = max(curlast, dp[v][j - 1] + (ll)W[v] * (S[j] - S[j - 1]));
		}
		pref[j].resize(n);
		pref[j][0] = {b[0][0], dp[b[0][1]][j]};
		for(int i = 1; i < n; ++i){
			pref[j][i][0] = b[i][0];
			pref[j][i][1] = max(pref[j][i - 1][1], dp[b[i][1]][j]);
		}
	}

}


ll arrival_time(ll Y){
	ll ans = Y;
	for(int i = 1; i < m; ++i){
		int pos = upper_bound(all(pref[i]), array<ll, 2>{ans, -1ll}) - pref[i].begin();
		ll val = 0;
		if(pos == 0) val = 0;
		else val = pref[i][pos - 1][1];
		ans = max(ans + X * (S[i] - S[i - 1]), val);
	}
	return ans;
}

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