제출 #847804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847804		sofapuden	추월 (IOI23_overtaking)	C++17	100 / 100	552 ms	45900 KiB

overtaking

#include<bits/stdc++.h>
#include "overtaking.h"

using namespace std;

typedef long long ll;

vector<pair<ll, int>> arr;
vector<vector<ll>> dp;
vector<vector<ll>> E;
vector<ll> nT;
vector<int> nW, nS;
ll l, n, speed, m;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
	E.resize(M, vector<ll> (N));
	dp.resize(M, vector<ll> (N, -1));
	for(int i = 0; i < N; ++i){
		if(W[i] > X){
			nT.push_back(T[i]);
			nW.push_back(W[i]);
		}
	}
	N = nT.size();
	T = nT;
	W = nW;
	l = L, n = N, speed = X, m = M, nS = S;
	arr.resize(N);
	for(int i = 0; i < N; ++i)arr[i] = {T[i], W[i]};
	sort(arr.begin(),arr.end());
	for(int i = 0; i < N; ++i)E[0][i] = arr[i].first;
	for(int i = 1; i < M; ++i){
		for(int j = 0; j < N; ++j){
			arr[j].first += 1ll * arr[j].second * (S[i] - S[i-1]);
			if(j)arr[j].first = max(arr[j].first, arr[j-1].first);
			E[i][j] = arr[j].first;
		}
		sort(arr.begin(),arr.end());
	}
    return;
}

long long f(int X, int Y){
	auto &d = dp[X][Y];
	if(~d)return d;
	if(Y == 0){
		return d = E[X][Y] + speed * (nS[m - 1] - nS[X]);
	}
	if(E[X][Y] == E[X][Y - 1]){
		return d = f(X, Y - 1);
	}
	//bin search
	int l = X + 1, r = m - 1, bes = m;
	while(l <= r){
		int i = (l + r) / 2;
		if(E[X][Y] + speed * (nS[i] - nS[X]) <= E[i][Y-1]){
			bes = i;
			r = i - 1;
		}
		else{
			l = i + 1;
		}
	}
	if(bes < m)return d = f(bes, Y - 1);
	return d = E[X][Y] + speed * (nS[m - 1] - nS[X]);
}

long long arrival_time(long long Y){
	// bin search
	int l = 0, r = n-1;
	while(l <= r){
		int i = (l + r) / 2;
		if(Y <= E[0][i]){
			r = i-1;
		}
		else{
			l = i + 1;
		}
	}
	if(r == -1){
		return Y + speed * (nS[m-1] - nS[0]);
	}
	int st = r;
	l = 1, r = m - 1;
	int bes = m;
	while(l <= r){
		int i = (l + r) / 2;
		if(Y + speed * (nS[i] - nS[0]) <= E[i][st]){
			bes = i;
			r = i - 1;
		}
		else{
			l = i + 1;
		}
	}
	if(bes < m)return f(bes, st);
	return Y + speed * (nS[m-1] - nS[0]);
}

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