Submission #1244713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244713		alexander707070	Overtaking (IOI23_overtaking)	C++20	100 / 100	1264 ms	69568 KiB

overtaking

#include<bits/stdc++.h>
#define MAXN 1007
using namespace std;

int n,m;
int station[MAXN];
long long speed[MAXN],start[MAXN];

pair<long long,int> st[MAXN][MAXN];
long long maxtim[MAXN][MAXN];
long long arrive[MAXN][MAXN];

long long dp[MAXN][MAXN];

bool cmp(pair<long long,int> fr,pair<long long,int> sc){
    if(fr.first!=sc.first)return fr.first<sc.first;
    return speed[fr.second] < speed[sc.second];
}

void build_timetable(){

    for(int i=1;i<=n;i++){
		arrive[1][i]=start[i];
		st[1][i]={start[i],i};
	}

    sort(st[1]+1,st[1]+n+1,cmp);

    for(int i=2;i<=m;i++){

		long long dist=station[i]-station[i-1];

		for(int f=1;f<=n;f++){

            int curr=st[i-1][f].second;

			maxtim[i-1][f]=st[i-1][f].first + dist*speed[curr];
			maxtim[i-1][f]=max(maxtim[i-1][f],maxtim[i-1][f-1]);

            arrive[i][curr]=maxtim[i-1][f];
            st[i][f]={arrive[i][curr],curr};
		}

		sort(st[i]+1,st[i]+n+1,cmp);
	}
}

int faster(int pos,long long tim){
    int l=0,r=n+1,tt;

    while(l+1<r){
        tt=(l+r)/2;

        if(st[pos][tt].first<tim){
            l=tt;
        }else{
            r=tt;
        }
    }

    return l;
}

void calc_dp(){
    for(int i=m;i>=1;i--){
        for(int f=1;f<=n;f++){
            
            if(i==m){
                dp[i][f]=st[i][f].first;
                continue;
            }

            int curr=faster(i,st[i][f].first);

            int l=i,r=m+1,tt;

            while(l+1<r){
                tt=(l+r)/2;

                if( faster(tt,st[i][f].first+(station[tt]-station[i])*speed[n+1]) != curr ){
                    r=tt;
                }else{
                    l=tt;
                }
            }

            if(r==m+1){
                dp[i][f]=st[i][f].first + (station[m]-station[i])*speed[n+1];
                continue;
            }

            dp[i][f]=dp[r][curr];
        }
    }
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S){
	n=N; m=M;

	for(int i=1;i<=m;i++)station[i]=S[i-1];
	for(int i=1;i<=n;i++)speed[i]=W[i-1];
	for(int i=1;i<=n;i++)start[i]=T[i-1];

    int sm=0;
    for(int i=1;i<=n;i++){
        if(speed[i]<=X)continue;

        sm++;
        speed[sm]=speed[i];
        start[sm]=start[i];
    }

    n=sm;
    speed[n+1]=X;

	build_timetable();
    calc_dp();
}

long long arrival_time(long long Y){
	long long tim=Y;

	int curr=faster(1,tim);
    int l=1,r=m+1,tt;

    while(l+1<r){
        tt=(l+r)/2;

        if( faster(tt,tim+(station[tt]-station[1])*speed[n+1]) != curr ){
            r=tt;
        }else{
            l=tt;
        }
    }

    if(r==m+1){
        return tim+(station[m]-station[1])*speed[n+1];
    }

    return dp[r][curr];
}

/*int main(){

	init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});

	cout<<arrival_time(0)<<"\n";
	cout<<arrival_time(50)<<"\n";

	return 0;
}*/

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