Submission #1205410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205410		PagodePaiva	Overtaking (IOI23_overtaking)	C++20	65 / 100	3594 ms	41796 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;
const int N = 1010;
ll tt[N][N];
vector <array <ll, 3>> v[N];
ll e[N][N];
ll prefmax[N][N];

void init(int L, int NN, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
    l = L;
    n = NN;
    t = T;
    x = X;
    for(auto valor : W)
        w.push_back(valor);
    m = M;
    for(auto valor : S)
        s.push_back(valor);
    for(int i = 0;i < n;i++){
        tt[i][0] = t[i];
    }
    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];
            v[j].push_back({tt[i][j-1], e[i][j], i});
        }
        sort(v[j].begin(), v[j].end());
        ll res = 0;
        for(auto [tmp, exp, i] : v[j]){
            //cout << tmp << ' ' << exp << ' ' << i << '\n';
            res = max(res, exp);
            tt[i][j] = res;
        }
        //cout << '\n';
    }

    return;
}

bool comp(array <ll, 3> a, array <ll,3> b){
    if(a[0] < b[0])
        return true;
    if(a[0] > b[0])
        return false;
    if(a[1] < b[1])
        return true;
    if(a[1] > b[1])
        return false;
    return (a[2] < b[2]);
}
long long arrival_time(long long Y){
    tt[n][0] = Y;
    for(int j = 1;j < m;j++){
        int l = 0, r = n-1, ans = -1;
        e[n][j] = tt[n][j-1] + (s[j]-s[j-1])*x;
        array <ll, 3> aux = {tt[n][j-1], e[n][j], n};
        //cout << tt[n][j-1] << ' ' << e[n][j] << ' ' << n << '\n';
        while(l <= r){
            int mid = (l+r)/2;
            if(comp(aux, v[j][mid])){
                r = mid-1;
            } 
            else{
                //cout << mid << '\n';
                ans = mid;
                l = mid+1;
            }
        }
        /*for(auto [a, b, c] : v[j]){
            cout << a << ' ' << b << ' ' << c << '\n';
        }
        cout << ans << ' ';*/
        tt[n][j] = max(e[n][j], (ans == -1 ? 0 : tt[v[j][ans][2]][j]));
        /*cout << tt[n][j] << '\n';
        cout << '\n';*/
    }
    return tt[n][m-1];
}

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