Submission #845147

#	Time	Username	Problem	Language	Result	Execution time	Memory
845147		Alfraganus	Overtaking (IOI23_overtaking)	C++17	39 / 100	3545 ms	79248 KiB

overtaking

#include "overtaking.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
typedef tree<ll, null_type, greater_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> Javohir;
#define fs first
#define ss second

vector<Javohir> a;
ll n, m, x;
vector<ll> s;

void init(int l, int a1, vector<ll> T, vector<int> w, int a2, int a3, vector<int> a4){
    n = a1;
    m = a3;
    x = a2;
    for(int i = 0; i < m; i ++)
        s.push_back(a4[i]);
    vector<vector<ll>> e(m, vector<ll> (n)), t(m, vector<ll> (n));
    a.resize(m);
    for(int i = 0; i < n; i ++)
        t[0][i] = T[i], a[0].insert(T[i]);
    for(int i = 1; i < m; i ++){
        for(int j = 0; j < n; j ++)
            e[i][j] = t[i - 1][j] + w[j] * (s[i] - s[i - 1]);
        for(int j = 0; j < n; j ++){
            ll ans = e[i][j];
            for(int x = 0; x < n; x ++){
                if(t[i - 1][x] < t[i - 1][j])
                    ans = max(ans, e[i][x]);
            }
            t[i][j] = ans;
            a[i].insert(ans);
        }
    }
}

ll arrival_time(ll y){
    for(int i = 1; i < m; i ++){
        ll e = y + x * (s[i] - s[i - 1]);
        ll k = a[i - 1].order_of_key(y - 1);
        if(k >= n)
            y = e;
        else
            y = max(e, *a[i].find_by_order(k));
    }
    return y;
}

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