Submission #1280390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280390		Luvidi	Overtaking (IOI23_overtaking)	C++20	65 / 100	3595 ms	17976 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
#define pb push_back


int l,n,x,m;
vector<ll> t,s,w;
vector<pll> a[1000];

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    l=L,n=N,t=T,x=X,m=M;
    for(int i:S)s.pb(i);
    for(int i:W)w.pb(i);
    pll c[n];
    for(int i=0;i<n;i++)c[i]={t[i],i};
    for(int i=0;i<m-1;i++){
        sort(c,c+n,[&](pll p1,pll p2){return make_pair(p1.fs,w[p1.sc])<make_pair(p2.fs,w[p2.sc]);});
        for(ll j=0,z=0;j<n;j++){
            z=max(z,c[j].fs+(s[i+1]-s[i])*w[c[j].sc]);
            a[i].pb({c[j].fs,z});
            c[j].fs=z;
        }
    }
    return;
}

long long arrival_time(long long y)
{   
    ll z=y;
    for(int i=0;i<m-1;i++){
        ll p=z+(s[i+1]-s[i])*x;
        pll tt={z,0};
        int j=lower_bound(a[i].begin(),a[i].end(),tt)-1-a[i].begin();
        if(j==-1)z=p;
        else z=max(p,a[i][j].sc);
    }
    return z;
}

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