Submission #1049165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049165		IUA_Hasin	Overtaking (IOI23_overtaking)	C++17	39 / 100	3552 ms	16220 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

#define ll              long long

using namespace std;

const int A = 1e3+10;

ll l, n, x, m;
vector<ll> t, w, s;
ll arr[A][A], brr[A][A];

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;
    x = X;
    m = M;

    for(int i=0; i<n; i++){
        ll a = T[i];
        ll b = W[i];
        t.push_back(a);
        w.push_back(b);
    }
    for(int i=0; i<m; i++){
        ll a = S[i];
        s.push_back(a);
    }




    return;
}

long long arrival_time(long long Y)
{
    for(int i=0; i<n+1; i++){
        for(int j=0; j<m; j++){
            arr[i][j] = 0;
            brr[i][j] = 0;
        }
    }

    for(int i=0; i<n; i++){
        arr[i][0] = t[i];
        //cout << arr[i][0] << " ";
    }
    //cout << 51 << endl;
    arr[n][0] = Y;

    for(int i=1; i<m; i++){
        vector<tuple<ll, ll, ll>> v;
        for(int j=0; j<n+1; j++){
            if(j==n){
                brr[j][i] = arr[j][i-1] + x*(s[i]-s[i-1]);
                v.push_back({arr[j][i-1], brr[j][i], j});
            } else {
                brr[j][i] = arr[j][i-1] + w[j]*(s[i]-s[i-1]);
                v.push_back({arr[j][i-1], brr[j][i], j});
            }            
        }
        sort(v.begin(), v.end());
        tuple<ll, ll, ll> f = v[0];
        ll curr = get<1>(f);

        // for(int j = 0; j<n+1; j++){
        //     cout << brr[j][i] << " ";
        // }
        // cout << 67 << endl;
        // for(int j = 0; j<n+1; j++){
        //     tuple<ll, ll, ll> temp = v[j];
        //     cout << get<0> (temp) << " " << get<1>(temp) << " " << get<2> (temp) << endl;
        // }
        // cout << 72 << endl;

        for(int j=0; j<n+1; j++){
            tuple<ll, ll, ll> temp = v[j];
            ll aaa = get<2>(temp);
            ll temp2 = get<1>(temp);
            ll ans = max(curr, temp2);
            curr = ans;
            arr[aaa][i] = ans;
        }

        // for(int j = 0; j<n+1; j++){
        //     cout << arr[j][i] << " ";
        // }
        // cout << 84 << endl;
    }   

    ll ans = arr[n][m-1];
    return ans;

}

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