Submission #1049204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049204		AIF_is_carving	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	348 KiB

overtaking

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef struct{
    ll time;
    ll skm;
    int idx;
    int id;
} zadu;

bool compareByAge(zadu p1, zadu p2) 
{ 
    if(p1.time < p2.time) return 1;
    else if(p1.time == p2.time){
        if(p1.skm < p2.skm) return 1;
        else if(p1.skm == p2.skm){
            if(p1.idx < p2.idx) return 1;
            else return 0;
        }
        else return 0;
    }
    else return 0;

} 

int l , n, x, m;
vector<ll> t, w, s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
    l = L, n = N, x = X, m = M;
    for(auto xx: T) t.push_back(xx);
    for(auto xx: W) w.push_back(xx);
    for(auto xx: S) s.push_back(xx);

    return;
}

long long arrival_time(long long Y){
    // for(auto x: w) cout<<x<<" ";
    //     cout<<"\n";
    vector<zadu> v;
    //cout<<n<<"\n";
    for(int i = 0; i<n; i++){
        zadu alz;
        alz.time = t[i];
        alz.skm = w[i];
        alz.id = i;
        alz.idx = i;
        v.push_back(alz);
    }

    zadu alz;
    alz.time = Y;
    alz.skm = x;
    alz.id = n;
    alz.idx = n;
    v.push_back(alz);

    // for(auto x: v){
    //     cout<<x.time<<" "<<x.skm<<" "<<x.id<<"\n";
    // }

    sort(v.begin(), v.end(), compareByAge);

    // for(auto x: v){
    //     cout<<x.time<<" "<<x.skm<<" "<<x.id<<"\n";
    // }

    for(int i = 1; i<m; i++){
        //cout<<i<<"\n";
        ll z = 0;
        for(int j =0; j<=n; j++){
            v[j].time = max(z, v[j].time + v[j].skm * (s[i] - s[i-1])); 
            z = v[j].time;

            //cout<<v[j].time<<" ";
        }
        //cout<<"\n";
        sort(v.begin(), v.end(), compareByAge);

        for(int j = 0; j<=n; j++){
            v[j].idx = j;
        }
    }

    int ans = 0;
    for(int i = 0; i<=n; i++){
        if(v[i].id == n) ans = v[i].time;
    }




    return ans;
}


// int main(){
//     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: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35