Submission #1074680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074680		Unforgettablepl	Overtaking (IOI23_overtaking)	C++17	65 / 100	3566 ms	34916 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    int L,N,X,M;
    vector<long long> T,W,S;
    vector<vector<pair<long long,long long>>> DP;
    vector<vector<pair<long long,long long>>> DPprev;
}

void gen() {
    DP = vector<vector<pair<long long,long long>>>(M);
    DPprev = vector<vector<pair<long long,long long>>>(M);
    for(int i=0;i<N;i++)DP[0].emplace_back(T[i],W[i]);
    sort(DP[0].begin(),DP[0].end());
    for(int i=1;i<M;i++) {
        for(int j=0;j<N;j++) {
            long long e = DP[i-1][j].first+DP[i-1][j].second*(S[i]-S[i-1]);
            int trans = -1;
            auto iter = lower_bound(DP[i-1].begin(),DP[i-1].end(),make_pair(DP[i-1][j].first,0ll))-DP[i-1].begin();
            trans = iter-1;
            if(trans!=-1)e=max(e,DP[i][trans].first);
            DP[i].emplace_back(e,DP[i-1][j].second);
            DPprev[i].emplace_back(e,DP[i-1][j].second);
        }
        sort(DP[i].begin(),DP[i].end());
    }
}

void init(int L,int N,vector<long long> T,vector<int> W,int X,int M,vector<int> S){
    W.emplace_back(X);
    ::L = L;
    ::N = N;
    ::T = T;
    for(int&i:W)::W.emplace_back(i);
    ::X = X;
    ::M = M;
    for(int&i:S)::S.emplace_back(i);
    gen();
}

long long arrival_time(long long Y){
    long long e = Y;
    for(int i=1;i<M;i++) {
        auto iter = lower_bound(DP[i-1].begin(),DP[i-1].end(),make_pair(e,0ll))-DP[i-1].begin();
        e+=X*(S[i]-S[i-1]);
        if(iter!=0)e = max(e,DPprev[i][iter-1].first);
    }
    return e;
}

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