제출 #857426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857426		mychecksedad	추월 (IOI23_overtaking)	C++17	39 / 100	3559 ms	9044 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;

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;
	W.pb(x);
}

ll dp[N][N];
ll arrival_time(ll Y){
	T.pb(Y);

	for(int i = 0; i <= n; ++i) dp[i][0] = T[i];
	for(int j = 1; j < m; ++j){
		// for(int i = 0; i <= n; ++i){
			// cout << i << ' ' << j << ' ' << dp[i][j - 1] << '\n';
		// }
		// en;
		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]));
		}
	}


	T.pop_back();

	return dp[n][m - 1];
}

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