Submission #1233841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233841		Sir_Ahmed_Imran	Overtaking (IOI23_overtaking)	C++17	65 / 100	3598 ms	71000 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1002
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int n, m, x;
vector<ll> d;
set<pll> r[MAXN];
ll t[MAXN][MAXN];

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
    ll e;
    vector<pii> w;
    x = X, n = N, m = M; 
    for(int i = 0; i < n; i++){
        w.append({W[i], i});
        t[i][0] = T[i];
    }
    sort(all(w));
    reverse(all(w));
    for(int i = 0; i < m; i++)
        d.append(S[i]);
    for(auto & [s, i] : w){
        if(s <= x) break;
        for(int j = 0; j < m - 1; j++){
            e = t[i][j] + s * (d[j + 1] - d[j]);
            if(!r[j].empty() && (*r[j].begin()).ff < t[i][j])
                e = max(e, (*(--r[j].lower_bound({t[i][j], 0}))).ss);
            r[j].add({t[i][j], e});
            t[i][j + 1] = e;
        }
    }
}

ll arrival_time(ll y){
    ll e;
    int s = x;
    t[n][0] = y;
    for(int j = 0; j < m - 1; j++){
        e = t[n][j] + s * (d[j + 1] - d[j]);
        if(!r[j].empty() && (*r[j].begin()).ff < t[n][j])
            e = max(e, (*(--r[j].lower_bound({t[n][j], 0}))).ss);
        t[n][j + 1] = e;
    }
    return t[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