Submission #1025027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025027		Mardonbekhazratov	Overtaking (IOI23_overtaking)	C++17	39 / 100	3536 ms	8528 KiB

overtaking

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

using namespace std;

int l,n,x,m;
vector<pair<long long,int>>t;
vector<int>s;
vector<vector<long long>>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(n,vector<long long>(m,0));
    for(int i=0;i<n;i++){
        e[i][0]=t[i].first;
        for(int j=1;j<m;j++){
            e[i][j]=e[i][j-1]+1LL*(s[j]-s[j-1])*t[i].second;
            for(int k=0;k<i;k++)
                if(e[k][j-1]<e[i][j-1])
                    e[i][j]=max(e[i][j],e[k][j]);
            // cout<<e[i][j]<<' ';
        }
        // cout<<'\n';
    }
    return;
}

long long arrival_time(long long Y){
    long long ans=Y;
    for(int i=1;i<m;i++){
        long long ex=ans+1LL*(s[i]-s[i-1])*x;
        for(int j=0;j<n;j++){
            if(e[j][i-1]<ans) ex=max(ex,e[j][i]);
        }
        ans=ex;
    }
    return ans;
}

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