Submission #854704

#	Time	Username	Problem	Language	Result	Execution time	Memory
854704		FairyWinx	Overtaking (IOI23_overtaking)	C++17	9 / 100	4 ms	600 KiB

overtaking

#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;

vector<vector<long long>> res;
vector<int> s;
vector<pair<int, long long>> t; // speed, time
int n, m;
int x;

void init(int l, int _n, vector<long long> _t, vector<int> _w, 
            int _x, int _m, vector<int> _s) {

    
    x = _x, n = _n, m = _m;
    s = _s;
    t.resize(n);
    for (int i = 0; i < n; ++i) {
        t[i].first = _w[i];
        t[i].second = _t[i];
    }
    sort(rall(t));
    while (t.size() && t.back().first <= x) {
        t.pop_back();
    }
    n = t.size();
    res.resize(m, vector<long long> (n, -1));
    s = _s;

    for (int i = 0; i < n; ++i) {
        res[0][i] = t[i].second;
    }
    for (int i = 0; i < m - 1; ++i) {
        for (int j = 0; j < n; ++j) {
            long long s1 = 1ll * (s[i + 1] - s[i]) * t[j].first;
            res[i + 1][j] = res[i][j] + s1;
            for (int k = 0; k < j; ++k) {
                if (res[i][j] > res[i][k] && res[i + 1][j] < res[i + 1][k]) {
                    res[i + 1][j] = max(res[i + 1][j], res[i + 1][k]);
                }
            }
        }
    }
}

long long arrival_time(long long y) {
    vector<long long> ans(m);
    ans[0] = y;
    for (int i = 0; i < m - 1; ++i) {
        ans[i + 1] = ans[i] + 1ll * (s[i + 1] - s[i]) * x;
        for (int j = 0; j < n; ++j) {
            if (res[i][j] < ans[i] && res[i + 1][j] > ans[i] + 1ll * (s[i + 1] - s[i]) * x)
                ans[i + 1] = max(ans[i], res[i + 1][j]);
        }
    }
    return ans.back();
}

#ifdef LOCAL
int main()
{
    // BEGIN SECRET
    const std::string input_secret = "XwWPuInrOjpekAwGKojzwKw3yVDtdkGS";
    const std::string output_secret = "mGlgT4yvr1qPbquFwkxRVh9hMn0Mrxoz";
    char secret[1000];
    assert(1 == scanf("%999s", secret));
    if (std::string(secret) != input_secret)
    {
        printf("%s\n", output_secret.c_str());
        printf("PV\n");
        printf("Possible tampering with the input\n");
        fclose(stdout);
        return 0;
    }
    // END SECRET
    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]);

    // BEGIN SECRET
    printf("%s\n", output_secret.c_str());
    printf("OK\n");
    // END SECRET
    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}
#endif

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