Submission #1026060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026060		Mardonbekhazratov	Overtaking (IOI23_overtaking)	C++17	65 / 100	3523 ms	34228 KiB

overtaking

#include "overtaking.h"
#include <iostream>
#include <array>
#include <tuple>
#include <algorithm>

using namespace std;

#define ll long long
#define ff first
#define ss second

int l,n,x,m;
vector<pair<long long,int>>t;
vector<int>s;
vector<vector<ll>>pref;
vector<vector<array<long long,3>>>e;


void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
    tie(l,n,x,m,s)=tie(L,N,X,M,S);
    t.resize(n);
    for(int i=0;i<n;i++){
        t[i].first=T[i];
        t[i].second=W[i];
    }
    sort(t.begin(),t.end());
    e.assign(m,vector<array<ll,3>>(n));
    pref.assign(m,vector<ll>(n+1));
    for(int i=0;i<n;i++) e[0][i]={t[i].ff,t[i].ss,i};
    for(int i=1;i<m;i++){
        pref[i][0]=0;
        int l=0;
        for(int j=0;j<n;j++){
            e[i][j]=e[i-1][j];
            if(j>0 && e[i-1][j-1][0]<e[i][j][0]) l=j;
            e[i][j][0]=max(pref[i][l],e[i][j][0]+1LL*(s[i]-s[i-1])*e[i][j][1]);
            pref[i][j+1]=max(pref[i][j],e[i][j][0]);
        }
        sort(e[i].begin(),e[i].end());
    }
}
     
long long arrival_time(long long Y){
    long long ans=Y;
    for(int i=1;i<m;i++){
        array<ll,3>gg={ans,0,0};
        int pos=lower_bound(e[i-1].begin(),e[i-1].end(),gg)-e[i-1].begin();
        ans=max(ans+1LL*(s[i]-s[i-1])*x,pref[i][pos]);
    }
    return ans;
}

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