Submission #1233984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233984		mariza	Overtaking (IOI23_overtaking)	C++20	65 / 100	3597 ms	47268 KiB

overtaking

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

typedef long long ll;
const ll N=1001;
#define MID ((l+r)/2)

ll n, t[N], w[N], m, s[N], tn;

ll z[N];
bool comp(ll a, ll b){
    return z[a]<z[b];
}

pair<ll,ll> li[N][N];

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
    n=N;
    for(ll i=0; i<n; i++){
        t[i]=T[i];
        w[i]=W[i];
    }
    tn=X;
    m=M;
    for(ll i=0; i<m; i++){
        s[i]=S[i];
    }

    ll x[n][m], e[n][m], idx[n];
    for(ll i=0; i<n; i++){
        x[i][0]=t[i];
        idx[i]=i;
    }
    for(ll j=1; j<m; j++){
        for(ll i=0; i<n; i++){
            e[i][j]=x[i][j-1]+w[i]*(s[j]-s[j-1]);
            z[i]=x[i][j-1];
        }
        sort(idx,idx+n,comp);

        ll c=0, ans=0;
        for(ll i=0; i<n; i++){
            if(i>0 && x[idx[i]][j-1]>x[idx[i-1]][j-1]) ans=max(ans,c);
            x[idx[i]][j]=max(e[idx[i]][j],ans);
            c=max(c,e[idx[i]][j]);
        }
    }

    for(ll j=0; j<m-1; j++){
        for(ll i=0; i<n; i++){
            li[j][i]={x[i][j],e[i][j+1]};
        }
        sort(li[j],li[j]+n);
        for(ll i=1; i<n; i++){
            li[j][i].second=max(li[j][i].second,li[j][i-1].second);
        }

        // cout<<"---"<<j<<"---"<<endl;
        // for(ll i=0; i<n; i++){
        //     cout<<li[j][i].first<<" "<<li[j][i].second<<endl;
        // }
        // cout<<endl;
    }

    return;
}

long long arrival_time(long long Y){
    ll curr=Y;
    for(ll j=0; j<m-1; j++){
        // cout<<curr<<endl;
        ll l=0, r=n-1, pos=-1;
        while(l<=r){
            if(li[j][MID].first<curr){
                pos=MID;
                l=MID+1;
            }
            else r=MID-1;
        }
        // cout<<pos<<endl<<endl;

        if(pos==-1) curr=curr+(s[j+1]-s[j])*tn;
        else curr=max(curr+(s[j+1]-s[j])*tn,li[j][pos].second);
    }
    return curr;
}

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