Submission #881929

#	Time	Username	Problem	Language	Result	Execution time	Memory
881929		irmuun	Overtaking (IOI23_overtaking)	C++17	39 / 100	3564 ms	600 KiB

overtaking

#include<bits/stdc++.h>
#include "overtaking.h"
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int l,n,x,m;
vector<ll>t;
vector<int>w,s;

void init(int L,int N,vector<ll>T,vector<int>W,int X,int M,vector<int>S){
    l=L; n=N; t=T; w=W; x=X; m=M; s=S;
}

ll arrival_time(ll Y){
    if(n==1){
        ll e[2],nxt[2];
        e[0]=t[0];
        e[1]=Y;
        for(int i=1;i<m;i++){
            nxt[0]=e[0]+1ll*(s[i]-s[i-1])*w[0];
            nxt[1]=e[1]+1ll*(s[i]-s[i-1])*x;
            if(e[0]<e[1]){
                nxt[1]=max(nxt[1],nxt[0]);
            }
            if(e[0]>e[1]){
                nxt[0]=max(nxt[0],nxt[1]);
            }
            e[0]=nxt[0];
            e[1]=nxt[1];
        }
        return e[1];
    }
    if(m==2){
        ll ans=Y+1ll*l*x;
        for(int i=0;i<n;i++){
            if(t[i]<Y){
                ll exp=1ll*t[i]+1ll*l*w[i];
                ans=max(ans,exp);
            }
        }
        return ans;
    }
    vector<ll>e(n+1),nxt(n+1);
    vector<pair<ll,int>>vec;
    w.pb(x);
    t.pb(Y);
    for(int i=0;i<=n;i++){
        e[i]=t[i];
    }
    for(int j=1;j<m;j++){
        for(int i=0;i<=n;i++){
            nxt[i]=e[i]+1ll*(s[j]-s[j-1])*w[i];
        }
        vec.clear();
        for(int i=0;i<=n;i++){
            vec.pb({e[i],i});
        }
        sort(all(vec));
        int L=0;
        ll mx=0;
        for(int i=0;i<=n;i++){
            if(vec[i].ff==vec[0].ff){
                continue;
            }
            if(vec[i].ff!=vec[i-1].ff){
                for(int k=L;k<i;k++){
                    mx=max(mx,nxt[vec[k].ss]);
                }
                L=i;
            }
            nxt[vec[i].ss]=max(nxt[vec[i].ss],mx);
        }
        for(int i=0;i<=n;i++){
            e[i]=max(e[i],nxt[i]);
        }
    }
    w.pop_back();
    t.pop_back();
    return e[n];
}

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