Submission #848330

#	Time	Username	Problem	Language	Result	Execution time	Memory
848330		math_rabbit_1028	Overtaking (IOI23_overtaking)	C++17	0 / 100	53 ms	2548 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int l, n, x, m;
vector<ll> t;
vector<int> w, s;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    l = L; n = N; t = T; w = W; x = X; m = M; s = S;
    return;
}

ll est[1010][1010], arr[1010][1010];

ll arrival_time(ll Y) {
    for (int i = 0; i < n; i++) arr[0][i] = t[i];
    arr[0][n] = Y;

    for (int j = 1; j < m; j++) {
        for (int i = 0; i < n; i++) est[j][i] = arr[j - 1][i] + (ll)w[i] * (s[j] - s[j - 1]);
        est[j][n] = arr[j - 1][n] + (ll)x * (s[j] - s[j - 1]);

        vector<pll> tlist;
        for (int i = 0; i <= n; i++) tlist.push_back({arr[j - 1][i], i});
        sort(tlist.begin(), tlist.end());

        ll last = 0, p = 0;
        for (int i = 0; i <= n; i++) {
            arr[j][tlist[i].second] = max(last, est[j][tlist[i].second]);
            last = max(last, est[j][tlist[i].second]);
        }
    }

    return arr[m - 1][n];
}

Compilation message (stderr)

overtaking.cpp: In function 'll arrival_time(ll)':
overtaking.cpp:31:22: warning: unused variable 'p' [-Wunused-variable]
   31 |         ll last = 0, p = 0;
      |                      ^

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