Submission #1061486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061486		dozer	Overtaking (IOI23_overtaking)	C++17	39 / 100	3561 ms	4696 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005



const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


ll t[MAXN], w[MAXN], s[MAXN], m, n, x;

ll compute(){
    vector<ll> curr(n, 0);

    for (ll i = 0; i < n; i++) curr[i] = t[i];

    for (ll i = 1; i < m; i++){
        vector<ll> todo(n);
        iota(todo.begin(), todo.end(), 0);
        sort(todo.begin(), todo.end(), [&](ll a, ll b){
            return make_pair(curr[a], w[a]) < make_pair(curr[b], w[b]);
        }); 
        ll dist = s[i] - s[i - 1];
        ll mini = 0;
        for (auto j : todo){
            ll to = curr[j] + dist * w[j];
            curr[j] = max(mini, to);
            mini = max(mini, to);
        }
    }
    return curr[n - 1];
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    n = N;
    m = M;
    for (ll i = 0; i < m; i++) s[i] = S[i];
    for (ll i = 0; i < n; i++) t[i] = T[i], w[i] = W[i];
    n++;
    w[n - 1] = X;
}

long long arrival_time(long long Y)
{
    t[n - 1] = Y;
    return compute();
}
/*
int main()
{
    fileio();
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}*/

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