Submission #1216395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216395		ASGA_RedSea	Overtaking (IOI23_overtaking)	C++20	39 / 100	3594 ms	484 KiB

overtaking

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll=long long;

#include"overtaking.h"


ll n,m,x;
vector<ll>t,w,s;



void init(int L,int N,vector<ll>T,vector<int>W,int X,int M,vector<int>S){
    n=N;m=M;t=T;x=X;
    for(auto&i:W)w.push_back(i);
    for(auto&i:S)s.push_back(i);
}

ll arrival_time(ll y){
    n++;
    t.push_back(y);
    w.push_back(x);

    vector<int>p(n);
    iota(p.begin(),p.end(),0);
    vector<ll>v=t;
    for(int i=1;i<m;i++){
        sort(p.begin(),p.end(),[&](int l,int r){return v[l]<v[r];});

        vector<ll>nv(n);

        ll mx=0;
        for(int j=0;j<n;j++){
            int k=j;
            while(k<n&&v[p[k]]==v[p[j]])k++;k--;

            for(int l=j;l<=k;l++)nv[p[l]]=max(mx,v[p[l]]+(s[i]-s[i-1])*w[p[l]]);
            for(int l=j;l<=k;l++)mx=max(mx,nv[p[l]]);

            j=k;
        }

        v=nv;

    }

    t.pop_back();
    w.pop_back();
    n--;

    return v[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