Submission #1242475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242475		urosk	Overtaking (IOI23_overtaking)	C++20	0 / 100	1 ms	324 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()
using namespace std;

using ll = int;
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];
ll x;
ll curt[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;
    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+1,id+1+n,1);
        sort(id+1,id+1+n,[](ll x,ll y){
            return curt[x]<curt[y];
        });
        for(ll ik = 1;ik<=n;ik++){
            ll i = id[ik];
            ll ig = id[ik-1];
            t[j][i] = max(t[j][ig],e[j][i]);
        }
    }
    n++;
    return;
}

long long arrival_time(long long Y)
{
    st[n] = Y;
    w[n] = x;
    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+1,id+1+n,1);
        sort(id+1,id+1+n,[](ll x,ll y){
            return curt[x]<curt[y];
        });
        for(ll ik = 1;ik<=n;ik++){
            ll i = id[ik];
            ll ig = id[ik-1];
            t[j][i] = max(t[j][ig],e[j][i]);
        }
    }
    return e[m][n];
}

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