Submission #1243449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243449		AlperenT_	Overtaking (IOI23_overtaking)	C++20	65 / 100	3595 ms	25924 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const ll maxn = 1000 + 10   , inf = 1e18 , mod = 998244353;
int n , l , m  ;
ll t[maxn] ;
int w[maxn] , s[maxn] ;
ll ti[maxn]  , ti2[maxn ]; 
vector <pair<pair<ll,ll> , ll > > vec[maxn] ;
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 ;
    m = M ; 
    rep(i , 0 , n-1){
        t[i] = T[i] ;
        w[i] = W[i]; 
    }
    w[n] = X ;
    rep(i , 0, m-1){
        s[i] = S[i] ;
    }
    rep(i , 0 ,n)ti[i] = t[i] ;
    rep(i , 1 , m-1){
        vector <pair<pair<ll,ll>  ,int> > vec2 ;
        rep(j , 0 ,n){
            ti2[j] = ti[j] + 1ll * (s[i]-s[i-1]) * w[j] ;
            vec2.pb({{ti[j],ti2[j]} , j});
        }
        sort(all(vec2)); 
        ll mn = -inf ;
        vec[i].pb({{-1,-1} , mn}) ;
        rep(j , 0 , sz(vec2)-1){
            int z = vec2[j].S ;
            ti[z] = max(mn , ti2[z]) ;
            mn = max(mn  , ti2[z]) ;
            vec[i].pb({vec2[j].F , mn}) ;
        }
    }
    return;
}

long long arrival_time(long long Y){
    rep(i , 1 , m-1){
        ll o = Y + 1ll*(s[i]-s[i-1]) * w[n] ;
        int x = upper_bound(all(vec[i]) , (pair<pair<ll,ll> , ll >){{Y,o} , n}) - vec[i].begin() -1 ;
        o = max(o , vec[i][x].S) ;
        Y = o ;
    }
    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