Submission #1068271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068271		amirhoseinfar1385	Overtaking (IOI23_overtaking)	C++17	65 / 100	3568 ms	126616 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1000+10;
long long n,dis[maxn],shib,m;
pair<long long,long long>all[maxn];
map<long long,vector<long long>>mp[maxn];
vector<pair<long long,long long>>mpmx[maxn];

long long solve(long long ind,long long y){
   // cout<<"solve: "<<ind<<" "<<y<<endl;
    if(ind==m-1){
        return y;
    }
    long long fake=shib*(dis[ind+1]-dis[ind])+y;
/*    for(auto x:mpmx[ind]){
        if(x.first>=y){
            break;
        }
        fake=max(fake,x.second);
    }*/
    int p=lower_bound(mpmx[ind].begin(),mpmx[ind].end(),make_pair(y,-1ll))-mpmx[ind].begin();
    if(p!=0){
        p--;
        fake=max(fake,mpmx[ind][p].second);
    }
    return solve(ind+1,fake);
}

void build(){
    for(long long i=0;i<m;i++){
        long long mx=0;
        for(auto x:mp[i]){
            long long fake=mx;
            for(auto y:x.second){
                mp[i+1][max(fake,x.first+(dis[i+1]-dis[i])*y)].push_back(y);
                mx=max(mx,x.first+(dis[i+1]-dis[i])*y);
          //      cout<<"wtf: "<<i<<" "<<x.first<<" "<<y<<endl;
            }
            mpmx[i].push_back(make_pair(x.first,mx));
        }
    }
}

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(long long i=0;i<n;i++){
        mp[0][T[i]].push_back(W[i]);
        all[i]=make_pair(T[i],W[i]);
    }
    shib=X;
    m=M;
    for(long long i=0;i<m;i++){
        dis[i]=S[i];
    }
    build();
    return;
}

long long arrival_time(long long Y)
{
    return solve(0,Y);
}

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