Submission #1025680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025680		Gray	Overtaking (IOI23_overtaking)	C++17	39 / 100	3567 ms	8284 KiB

overtaking

#include "overtaking.h"
#include <algorithm>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
#define pll pair<ll, ll>
using namespace std;

ll l, n, x, m;
vector<ll> leave;
vector<ll> speed;
vector<ll> stat;
vector<vector<ll>> t;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    l=L; n=N; x=X; m=M;
    t.resize(m, vector<ll>(n+1));
    leave = T;
    leave.push_back(0);
    speed.resize(n+1); speed[n]=x;
    stat.resize(m);
    for (ll i=0; i<n; i++) {speed[i]=W[i];}
    for (ll i=0; i<m; i++) {stat[i]=S[i];}
}
long long arrival_time(long long Y)
{
    leave[n]=Y;
    vector<ll> ord;
    for (ll i=0; i<=n; i++){
        ord.push_back(i);
        t[0][i]=leave[i];
    }
    sort(ord.begin(), ord.end(), [&](ll bus1, ll bus2)->bool{
        if (t[0][bus1]!=t[0][bus2]) return t[0][bus1]<t[0][bus2];
        return speed[bus1]<speed[bus2];
    });
    for (ll i=1; i<m; i++){
        for (ll j=0; j<=n; j++){
            t[i][j]=t[i-1][j]+speed[j]*(stat[i]-stat[i-1]);
        }
        for (ll j=1; j<=n; j++){
            t[i][ord[j]]=max(t[i][ord[j]], t[i][ord[j-1]]);
        }
        sort(ord.begin(), ord.end(), [&](ll bus1, ll bus2)->bool{
            if (t[i][bus1]!=t[i][bus2]) return t[i][bus1]<t[i][bus2];
            return speed[bus1]<speed[bus2];            
        });
    }
    return t[m-1][n];
}

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