Submission #1068401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068401		AmirAli_H1	Overtaking (IOI23_overtaking)	C++17	65 / 100	3553 ms	39508 KiB

overtaking

// In the name of Allah

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

typedef			long long				ll;
typedef			pair<int, int>			pii;
typedef			pair<ll, ll>			pll;

#define			F						first
#define			S						second
#define			endl					'\n'
#define			sep						' '
#define			pb						push_back
#define			Mp						make_pair
#define			all(x)					(x).begin(),(x).end()
#define			len(x)					((ll) (x).size())

const int maxn = 1000 + 4;
const ll oo = 8e18 + 4;

int n, m; ll X;
pll A[maxn]; ll R[maxn]; int ind;
ll dp[maxn][maxn]; int arr[maxn];
pll dpx[maxn][maxn];

bool cmp(int i, int j) {
	return (dp[ind][i] < dp[ind][j]);
}

void init(int L, int Nx, vector<ll> T, vector<int> W, int Z, int Mx, vector<int> S) {
	n = Nx; m = Mx; X = Z;
	for (int i = 0; i < n; i++) A[i] = Mp(T[i], W[i]);
	for (int i = 0; i < m; i++) R[i] = S[i];
	
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (i == 0) dp[i][j] = A[j].F;
			else {
				dp[i][j] = (dp[i - 1][j] + (R[i] - R[i - 1]) * A[j].S);
			}
		}
		if (i - 1 >= 0) {
			ind = i - 1;
			iota(arr, arr + n, 0); sort(arr, arr + n, cmp);
			ll x1 = -oo, x2 = -oo;
			for (int r = 1; r < n; r++) {
				int j1 = arr[r - 1], j2 = arr[r];
				x2 = max(x2, dp[i][j1]);
				if (dp[i - 1][j1] != dp[i - 1][j2]) x1 = x2;
				dp[i][j2] = max(dp[i][j2], x1);
			}
			for (int j = 0; j < n; j++) {
				dpx[i - 1][j] = Mp(dp[i - 1][j], dp[i][j]);
			}
			sort(dpx[i - 1], dpx[i - 1] + n);
			for (int j = 1; j < n; j++) {
				dpx[i - 1][j].S = max(dpx[i - 1][j].S, dpx[i - 1][j - 1].S);
			}
		}
	}
	
	return ;
}

ll arrival_time(ll Y) {
	ll res = Y;
	for (int i = 1; i < m; i++) {
		ll resx = res + (R[i] - R[i - 1]) * X;
		int r = lower_bound(dpx[i - 1], dpx[i - 1] + n, Mp(res, -oo)) - dpx[i - 1] - 1;
		if (r >= 0) resx = max(resx, dpx[i - 1][r].S);
		res = resx;
	}
	return res;
}

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