Submission #1229645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229645		virgoliny	Overtaking (IOI23_overtaking)	C++20	39 / 100	3592 ms	8260 KiB

overtaking

#include "overtaking.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<ll>> res;
ll x, m, l, n;
vector<ll> t, w, s1;
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;
    m=M;
    vector<vector<ll>>().swap(res);
    vector<ll>().swap(w);
    vector<ll>().swap(s1);
    res.resize(N+1, vector<ll>(M));
    w.resize(N+1);
    s1.resize(M+1);
    for(int i=0; i<N; i++)w[i]=W[i];
    for(int i=0; i<M; i++)s1[i]=S[i];
    w[N]=X;
    for(int i=0; i<N; i++)res[i][0]=T[i];
    return;
}

long long arrival_time(long long Y){
    res[n][0]=Y;
    ll cnt=0;
    set<tuple<ll, ll, ll>> s;
    for(int i=0; i<=n; i++){s.insert({res[i][0], w[i], i});}
    for(int i=1; i<m; i++){
        ll o=-1;
        for(auto& [x, o1, y]: s){
        o=max(o, x+(w[y]*(s1[i]-s1[i-1])));
        //cout<<i<<" "<<x<<" "<<y<<" "<<w[y]<<" "<<x+(w[y]*(s1[i]-s1[i-1]))<<endl;
        res[y][i]=o;
        }
        set<tuple<ll, ll, ll>>().swap(s);
        for(int j=0; j<=n; j++)s.insert({res[j][i], w[j], j});
    }
    /*for(int j=0; j<m; j++){
    cout<<j<<endl;
    for(int i=0; i<=n; i++){
    cout<<res[i][j]<<" ";
    }
    cout<<endl;
    }*/
    return res[n][m-1];
}

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