Submission #1242493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242493		urosk	Overtaking (IOI23_overtaking)	C++20	65 / 100	3599 ms	33348 KiB

overtaking

#include "overtaking.h"
#include "bits/stdc++.h"
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define si(a_) (ll)(a_.size())
#define all(a_) a_.begin(),a_.end()
#define here cerr<<"========================================\n"
#define dbg(X_) cerr<<#X_<<": "<<X_<<endl;
#define ceri(a_,l_,r_) {for(ll i_=l_;i_<=r_;i_++) cerr<<a_[i_]<<" ";cerr<<endl;}
using namespace std;

using ll = long long;
using pll = pair<ll,ll>;

const ll maxn = 1005;

ll n,l,m;
ll st[maxn],w[maxn];
ll s[maxn];
ll e[maxn][maxn];
ll t[maxn][maxn];
ll id[maxn][maxn];
ll x;
ll curt[maxn];
ll pmx[maxn][maxn];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n = N,l = L,m = M,x = X;
    for(ll i = 1;i<=n;i++) st[i] = T[i-1];
    for(ll i = 1;i<=n;i++) w[i] = W[i-1];
    for(ll i = 1;i<=m;i++) s[i] = S[i-1];
    for(ll i = 1;i<=n;i++) t[1][i] = st[i];
   for(ll j = 2;j<=m;j++){
        for(ll i = 1;i<=n;i++){
            e[j][i] = t[j-1][i] + w[i]*(s[j]-s[j-1]);
        }
        for(ll i = 1;i<=n;i++) curt[i] = t[j-1][i];;
        iota(id[j]+1,id[j]+1+n,1);
        sort(id[j]+1,id[j]+1+n,[](ll x,ll y){
            return curt[x]<curt[y];
        });
        ll last = 0;
        for(ll ik = 1;ik<=n;ik++){
            ll i = id[j][ik];
            ll ig = id[j][ik-1];
            pmx[j][i] = max(pmx[j][ig],e[j][i]);
        }
        for(ll ik = 1;ik<=n;ik++){
            ll i = id[j][ik];
            ll ig = id[j][ik-1];
            if(curt[i]!=curt[ig]) last = ig;
            t[j][i] = max(pmx[j][last],e[j][i]);
        }
        // cerr<<w[n]*(s[j]-s[j-1])<<endl;
        // ceri(e[j],1,n);
        // ceri(t[j],1,n);
    }
    return;
}
long long arrival_time(long long Y)
{
    ll y = Y;
    // here;
    // dbg(Y);
    for(ll j = 2;j<=m;j++){
        ll mxt = y+(s[j]-s[j-1])*x;
        ll tl = 1,tr = n,mid,rez = -1;
        while(tl<=tr){
            mid = (tl+tr)/2;
            if(t[j-1][id[j][mid]]<y) rez = mid,tl = mid+1;
            else tr = mid-1;
        }
        if(rez==-1) y = mxt;
        else y = max(mxt,pmx[j][id[j][rez]]);
        // cerr<<w[n]*(s[j]-s[j-1])<<endl;
        // ceri(e[j],1,n);
        // ceri(t[j],1,n);
    }
    return y;
}

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