Submission #1188371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188371		MatteoArcari	Overtaking (IOI23_overtaking)	C++20	39 / 100	3589 ms	8360 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;

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

void init(int _l, int _n, vector<ll> _t, vi _w, int _x, int _m, vi _s) {
    n = _n; m = _m; x = _x; l = _l; t = _t;
    w = vector<ll>(_w.begin(), _w.end());
    s = vector<ll>(_s.begin(), _s.end());

    w.push_back(x);
    t.push_back(0);

    ex.resize(m);
    for (int i = 0; i < m; i++) {
        ex[i] = s[i] * w[0] + t[0];
    }
}

ll arrival_time(ll y) {
    t[n] = y;
    vector<vector<ll>> dp(m, vector<ll>(n + 1));
    dp[0] = t;

    vector<pair<ll, int>> srt(n + 1);
    for (int i = 0; i <= n; i++) {
        srt[i] = {dp[0][i], i};
    }

    sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
        if (_i.first == _j.first) return w[_i.second] < w[_j.second];
        return _i.first < _j.first;
    });

    for (int j = 1; j < m; j++) {
        ll ma = 0;
        for (auto [tm, i]: srt) {
            ma = max(ma, dp[j - 1][i] + w[i] * (s[j] - s[j - 1]));
            dp[j][i] = ma;
        }

        for (int i = 0; i <= n; i++) {
            srt[i] = {dp[j][i], i};
        }
        sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
            if (_i.first == _j.first) return w[_i.second] < w[_j.second];
            return _i.first < _j.first;
        });
    } 
    return dp[m - 1][n];
}

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