Submission #1095592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095592		abdzag	Overtaking (IOI23_overtaking)	C++17	39 / 100	3538 ms	16280 KiB

overtaking

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

using namespace std;
typedef long long ll;
ll inf = 1e9;

vector<vector<ll>> init_arrival_time;
vector<ll> t, w, s;
ll l, n,x, m;
vector<vector<ll>> get_arrivial_time(){
    ll n = t.size();
    vector<vector<ll>> ans(m, vector<ll>(n));
    ans[0] = t;
    // for(auto a:ans[0])cout<<a<<" ";
    // cout<<endl;
    for(int i=1; i<m; i++){
        vector<pair<ll,ll>> vec;
        for(int j=0; j<n; j++)vec.push_back({ans[i-1][j], j});
        sort(vec.begin(), vec.end());
        ll cur_max = -inf, cur_max2 = -inf;
        for(int j=0; j<n; j++){
            ll val = vec[j].first + w[vec[j].second] * (s[i] - s[i-1]);
            if(j and vec[j-1].first == vec[j].first){
                val = max(val, cur_max2);
            }
            else {
                cur_max2 = cur_max;
                val = max(val, cur_max);
            }
            cur_max = max(val, cur_max);
            ans[i][vec[j].second] = val;
        }
        // for(auto a:ans[i])cout<<a<<" ";
        // cout<<endl;
    }
    return ans;
}

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    t = T;
    l = L;
    n = N;
    x = X;
    m = M;
    w = vector<ll>(n);
    for(int i=0; i<n; i++)w[i] = W[i];
    s = vector<ll>(m);
    for(int i=0; i<m; i++)s[i] = S[i];
    init_arrival_time = get_arrivial_time();
    return;
}

long long arrival_time(long long Y)
{
    t.push_back(Y);
    w.push_back(x);
    auto ans = get_arrivial_time();
    ll res = ans[m-1][n];
    t.pop_back();
    w.pop_back();
    return res;
}

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