Submission #1241442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241442		dosts	Overtaking (IOI23_overtaking)	C++20	39 / 100	3536 ms	16196 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;
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_;
    t.assign(M,vi(N,inf));
    vi order[M];
    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;
        }
        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 mx = 0;
    for (int j = 0;j<N;j++) {
        if (t[station][j] < tm) {
            mx = max(mx,t[station+1][j]);
        }
    }
    return mx;
}

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: 0 / 26
• Subtask 5: 0 / 35