Submission #1008651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008651		aaaaaarroz	Overtaking (IOI23_overtaking)	C++17	65 / 100	3590 ms	26936 KiB

overtaking

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int l, n, m, x;
vector<ll> t; 
vector<ll> W;
vector<ll> s; 
vector<vector<pair<ll, ll>>> tiempos(1009); 
vector<vector<ll>> dp(1009, vector<ll>(1009)); 
void init(int L, int N, vector<ll> T, vector<int> w, int X, int M, vector<int> S) {
    l = L;
    n = N;
    m = M;
    x = X;
    t.clear();
    W.clear();
    s.clear();
    for (int i = 0; i < 1009; ++i){
		tiempos[i].clear();
	}
    for (int i = 0; i < N; i++) {
        if (w[i] > x) {
            W.push_back(w[i]);
            t.push_back(T[i]);
        }
    }
    for (int i = 0; i < M - 1; i++) s.push_back(S[i + 1] - S[i]);
    n = t.size();
    for (int i = 0; i < n; i++){
		dp[i][0] = t[i];
	}
    for (int j = 1; j < m; j++) {
        vector<pair<ll, ll>> x;
        for (int i = 0; i < n; i++){
			x.push_back(make_pair(dp[i][j - 1], i));
		}
        sort(x.begin(), x.end());
        ll mx = 0, mx2 = 0;
        tiempos[j].push_back(make_pair(-1, 0));
        for (int i = 0; i < n; i++) {
            if (i != 0 && x[i].first > x[i - 1].first) mx = max(mx, mx2);
            int v = x[i].second;
            dp[v][j] = max(mx, dp[v][j - 1] + W[v] * s[j - 1]);
            mx2 = max(mx2, dp[v][j]);
            tiempos[j].push_back(make_pair(x[i].first, max(mx, mx2)));
        }
    }
}
ll arrival_time(ll arrival) {
    ll cur = arrival;
    for (int i = 1; i < m; i++) {
        int idx = lower_bound(tiempos[i].begin(), tiempos[i].end(), make_pair(cur, -1LL)) - tiempos[i].begin() - 1;
        cur = max(cur + s[i - 1] * x, tiempos[i][idx].second);
    }
    return cur;
}

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