Submission #1241448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241448		dosts	Overtaking (IOI23_overtaking)	C++20	65 / 100	3595 ms	25672 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;
const int inf = 2e18;
int M,X,N;
vi S;
vector<vi> t;
vector<vi> vects;
vector<vi> order;
void init(signed L, signed N_, std::vector<int> T, std::vector<signed> W, signed X_, signed M_, std::vector<signed> S_)
{
    S = vi(all(S_));
    X = X_;
    M = M_;
    N = N_;
    order.resize(M);
    vects.resize(M);
    t.assign(M,vi(N,inf));
    for (int i = 0;i<N;i++) t[0][i] = T[i];
    for (int i = 0;i<M;i++) {
        order[i] = vi(N);
        iota(all(order[i]),0ll);
    }
    sort(all(order[0]),[&](int a,int b) {
        return pii{t[0][a],W[a]} < pii{t[0][b],W[b]};
    });
    for (int i=1;i<M;i++) {
        int worst = 0;
        for (auto it : order[i-1]) {
            worst = max(worst,t[i-1][it]+(S[i]-S[i-1])*W[it]);
            t[i][it] = worst;
            vects[i-1].push_back(t[i][it]);
        }
        sort(all(order[i]),[&](int a,int b) {
            return pii{t[i][a],W[a]} < pii{t[i][b],W[b]};
        });
    }
    return;
}

int before(int station,int tm) {
    //buraya t'den < gelenlerin bi sonrakine gidiş maxı
    int l = 1;
    int r = vects[station].size();
    while (l<=r) {
        int m = (l+r) >> 1;
        if (t[station][order[station][m-1]] < tm) l = m+1;
        else r = m-1;
    }
    if (!r) return 0;
    return vects[station][r-1];
}

int arrival_time(int Y)
{
    int curt = Y;
    for (int i = 0;i<M-1;i++) {
        curt = max(curt+(S[i+1]-S[i])*X,before(i,curt));
    }
    return curt;
}

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