Submission #1205017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205017		PagodePaiva	Overtaking (IOI23_overtaking)	C++20	19 / 100	83 ms	8552 KiB

overtaking

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

using namespace std;

ll l, n;
vector <ll> t;
vector <ll> w;
ll x, m;
vector <ll> s;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
    l = L;
    n = N;
    t = T;
    x = X;
    for(auto valor : W)
        w.push_back(valor);
    m = M;
    for(auto valor : S)
        s.push_back(valor);
    return;
}

const int N = 1010;
ll tt[N][N];
ll e[N][N];

void rev(vector <array<ll, 3>> &v){
    vector <array <ll, 3>> ans;
    stack <array <ll, 3>> aux;
    for(auto [a, b, c] : v){
        if(aux.empty())
            aux.push({a, b, c});
        else{
            if(aux.top()[0] == a)
                aux.push({a, b, c});
            else{
                while(!aux.empty()){
                    ans.push_back(aux.top());
                    aux.pop();
                }
                aux.push({a, b, c});
            }
        }
    }
    while(!aux.empty()){
        ans.push_back(aux.top());
        aux.pop();
    }
    v = ans;
    return;
}

long long arrival_time(long long Y){
    t.push_back(Y);
    w.push_back(x);
    for(int i = 0;i <= n;i++){
        tt[i][0] = t[i];
    }
    vector <array <ll, 3>> v;
    for(int j = 1;j < m;j++){
        for(int i = 0;i <= n;i++){
            e[i][j] = tt[i][j-1] + (s[j]-s[j-1])*w[i];
            if(j == 1){
                v.push_back({tt[i][j-1], e[i][j], i});
            }
        }
        if(j == 1){
            sort(v.begin(), v.end());
        }
        else{
            for(int i = 0;i <= n;i++){
                v[i][0] = tt[v[i][2]][j-1];
                v[i][1] = e[v[i][2]][j];
            }
            rev(v);
        }
        ll res = 0;
        for(auto [tmp, exp, i] : v){
            //cout << tmp << ' ' << exp << ' ' << i << '\n';
            res = max(res, exp);
            tt[i][j] = res;
        }
        //cout << '\n';
    }
    ll ans = tt[n][m-1];
    t.pop_back();
    w.pop_back();
    return ans;
}

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