Submission #1078064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078064		MohamedFaresNebili	Overtaking (IOI23_overtaking)	C++17	39 / 100	3546 ms	8408 KiB

overtaking

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

        using namespace std;

        int L, N, X, M;
        vector<int> S, W;
        vector<long long> T;

        bool comp(array<long long, 3> U, array<long long, 3> V) {
            if(U[0] != V[0]) return U[0] < V[0];
            if(U[1] != V[1]) return U[1] < V[1];
            return U[2] < V[2];
        }

        void init(int _L, int _N, vector<long long> _T, vector<int> _W, int _X, int _M, vector<int> _S) {
            L = _L, N = _N, X = _X, M = _M;
            swap(S, _S);
            swap(W, _W);
            swap(T, _T);
            W.push_back(X);
        }

        long long arrival_time(long long Y) {
            vector<vector<long long>> A(N + 1, vector<long long> (M));
            for(int l = 0; l < N; l++)
                A[l][0] = T[l];
            A[N][0] = Y;
            for(int i = 1; i < M; i++) {
                vector<array<long long, 3>> ord;
                for(int l = 0; l <= N; l++) {
                    A[l][i] = A[l][i - 1] + (long long)W[l] * (long long)(S[i] - S[i - 1]);
                    ord.push_back({A[l][i - 1], W[l], l});
                }
                sort(ord.begin(), ord.end(), comp);
                long long mx = -1;
                for(int l = 0; l <= N; l++) {
                    A[ord[l][2]][i] = max(A[ord[l][2]][i], mx);
                    mx = A[ord[l][2]][i];
                }
            }

            return A[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