Submission #847897

#	Time	Username	Problem	Language	Result	Execution time	Memory
847897		MuntherCarrot	Overtaking (IOI23_overtaking)	C++17	39 / 100	3522 ms	600 KiB

overtaking

// by me
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")

#include "overtaking.h"

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()
const int MOD = 1e9 + 7, SZ = 1e5 + 10, INF = 1e9;

// struct
#define pii pair<ll, int>
#define val first
#define idx second

vector<ll> t;
vector<int> w, s;
int 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;
    t = T, w = W, s = S;
    w.push_back(X);
    t.resize(n + 1);
    return;
}
long long arrival_time(long long Y)
{
    t[n] = Y;
    vector<pii> vec(n + 1);
    for(int i = 0; i <= n; i++){
        vec[i] = {t[i], i};
    }
    sort(all(vec), [](pii a, pii b){
        if(a.val == b.val){
            return w[a.idx] < w[b.idx];
        }
        return a.val < b.val;
    });
    while(vec.back().idx != n){
        vec.pop_back();
    }
    for(int j = 1; j < m; j++){
        ll mx = 0;
        for(pii &x : vec){
            x.val = max(x.val + 1ll * w[x.idx] * (s[j] - s[j - 1]), mx);
            mx = max(mx, x.val);
        }
        sort(all(vec), [](pii a, pii b){
            if(a.val == b.val){
                return w[a.idx] < w[b.idx];
            }
            return a.val < b.val;
        });
        while(vec.back().idx != n){
            vec.pop_back();
        }
    }

    ll ans = 0;
    for(pii &x : vec){
        if(x.idx == n){
            ans = x.val;
        }
    }

    return ans;
}
// int32_t main(){
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     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;
// }
// by me

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