제출 #1233834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233834		Ghulam_Junaid	추월 (IOI23_overtaking)	C++20	65 / 100	3595 ms	33400 KiB

overtaking

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

#define F first
#define S second

typedef long long ll;

const int MXN = 1005;
int n, m, l;
vector<ll> T;
vector<int> W, S;
vector<vector<ll>> dp;
vector<pair<pair<ll, ll>, int>> store[MXN];

void init(int L, int N, vector<ll> tt, vector<int> ww, int xx, int M, vector<int> ss){
    n = N, l = L, m = M;
    ww.push_back(xx), tt.push_back(1e18);
    W = ww, T = tt, S = ss;

    dp.resize(n + 1);
    for (int i = 0; i <= n; i ++){
        dp[i].resize(m);
        dp[i][0] = T[i];
    }

    vector<pair<pair<ll, ll>, int>> order;
    for (int j = 1; j < m; j ++){
        order.clear();
        for (int i = 0; i < n; i ++)
            order.push_back({{dp[i][j - 1], W[i]}, i});
        sort(order.begin(), order.end());

        ll mx = 0;
        for (auto [P, i] : order){
            mx = max(mx, dp[i][j - 1] + 1ll * W[i] * (S[j] - S[j - 1]));
            dp[i][j] = mx;
        }

        order.clear();
        for (int i = 0; i < n; i ++){
            if (W[i] <= W[n]) continue;
            order.push_back({{dp[i][j - 1], dp[i][j]}, i});
        }
        sort(order.begin(), order.end());

        for (int i = 1; i < order.size(); i ++)
            order[i].F.S = max(order[i].F.S, order[i - 1].F.S);
        store[j] = order;
    }
    return;
}

ll arrival_time(ll Y){
    T[n] = Y;

    ll prv = Y;
    for (int j = 1; j < m; j ++){
        int pos = lower_bound(store[j].begin(), store[j].end(), (pair<pair<ll, ll>, int>){{prv, -1}, -1}) - store[j].begin() - 1;
        ll mx = 0;
        if (pos >= 0) mx = store[j][pos].F.S;
        mx = max(mx, prv + 1ll * W[n] * (S[j] - S[j - 1]));
        prv = mx;
    }
    return prv;
}

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