Submission #1213352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213352		Nelt	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	840 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1005;
ll t[N][N];
ll v[N], s[N];
ll n, m;
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, m = M;
    for (ll i = 0; i < n; i++)
        t[i][0] = T[i];
    for (ll i = 0; i < n; i++)
        v[i] = W[i];
    v[n] = X;
    for (ll i = 0; i < m; i++)
        s[i] = S[i];
}

long long arrival_time(long long Y)
{
    t[n][0] = Y;
        vector<pair<ll, ll>> tmp;
    for (ll i = 0; i <= n; i++)
        tmp.push_back(make_pair(-v[i], i));
 	sort(tmp.begin(), tmp.end());
    for (ll i = 1; i < m; i++)
    {
        ll mx[n + 1];
        for (ll x = 0; x <= n; x++) 
        {
            ll j = tmp[x].second;
            t[j][i] = t[j][i - 1] + v[j] * (s[i] - s[i - 1]);
            mx[x] = max(x > 0 ? mx[x - 1] : 0, t[j][i]);
            ll pos = lower_bound(tmp.begin(), tmp.end(), make_pair(-v[j], -1ll)) - tmp.begin() - 1;
            if (pos >= 0)
                t[j][i] = max(t[j][i], mx[pos]);
        }
    }
    return t[n][m - 1];
}

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