Submission #1065698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065698		cpdreamer	Overtaking (IOI23_overtaking)	C++17	39 / 100	3551 ms	15964 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define V vector
#define F first
#define pb push_back
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
struct bus{
    ll departure;
    ll speed;
};
bus A[(int)2000];
V<int>stat(2000);
int l,n,m,x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    for(int i=0;i<N;i++){
        A[i].departure=T[i];
        A[i].speed=W[i];
    }
    l=L,n=N,m=M,x=X;
    for(int i=0;i<M;i++){
        stat[i]=S[i];
    }

}
struct tim{
    ll expected;
    ll arrival;
};
bool sorted( tim a,  tim b){
    return a.arrival<b.arrival;
}
long long arrival_time(long long Y)
{
    A[n]={Y,x};
    tim stations[m][n+1];
    V<tim>precedor(n+1);
    for(int i=0;i<=n;i++) {
        stations[0][i].arrival = A[i].departure;
        precedor[i].arrival=stations[0][i].arrival;
    }

    for(int i=1;i<m;i++){
        for(int j=0;j<=n;j++){
            stations[i][j].expected=stations[i-1][j].arrival+(stat[i]-stat[i-1])*A[j].speed;
            precedor[j].expected=stations[i][j].expected;
        }
        sort(all(precedor),sorted);
        ll maximum[n+1];
        maximum[0]=precedor[0].expected;
        for(int j=1;j<=n;j++){
            maximum[j]=max(maximum[j-1],precedor[j].expected);
        }
        for(int j=0;j<=n;j++){
            ll comp=stations[i-1][j].arrival;
            int left=0,right=n;
            int ans=-1;
            while(left<=right){
                int middle=(left+right)/2;
                if(precedor[middle].arrival<comp){
                    ans=middle;
                    left=middle+1;
                }
                else
                    right=middle-1;
            }
            if(ans!=-1)
                stations[i][j].arrival=max(maximum[ans],stations[i][j].expected);
            else
                stations[i][j].arrival=stations[i][j].expected;
        }
        for(int j=0;j<=n;j++){
            precedor[j].arrival=stations[i][j].arrival;
        }
    }
    return stations[m-1][n].arrival;
}

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