Submission #1049275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049275		AIF_is_carving	Overtaking (IOI23_overtaking)	C++17	65 / 100	3558 ms	42716 KiB

overtaking

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

ll N, M, L, X;
vector<ll> T, W , S;
const int sizex = 1e3+5;
vector<zadu> kotokisu[sizex];
ll dp[sizex][sizex];

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;

} 

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, L = l, X = x;
    for(auto x: t) T.push_back(x);
    for(auto x: w) W.push_back(x);
    for(auto x: s) S.push_back(x);

    vector<zadu> v;
    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);
    }

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

    for(int i = 1; i<m; i++){
        for(int j = 0; j<n; j++){
            kotokisu[i-1].push_back(v[j]);
            dp[v[j].id][i-1] = v[j].time;
        }

        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;
        }
        sort(v.begin(), v.end(), compareByAge);

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

    for(int j = 0; j<n; j++){
        kotokisu[m-1].push_back(v[j]);
        dp[v[j].id][m-1] = v[j].time;
    }

    return;
}

long long arrival_time(long long Y){

    float NN = N - 0.5;
    zadu alz = {Y, X, NN, N};

    for(int i = 0; i<M-1; i++){
        int hi = N, lo = -1;
        while(hi - lo>1){
            int mid = (hi + lo)/2;

            if(compareByAge(alz, kotokisu[i][mid])) hi = mid;
            else lo = mid;

            //cout<<hi<<" "<<mid<<"\n";
        }


        //cout<<lo<<" "<<alz.time<<" ";

        alz.idx = lo+ 0.5;
        if(lo == -1){
            alz.time = alz.time + X*(S[i+1] - S[i]);
        }
        else{
            int j = kotokisu[i][lo].id;
            //cout<<dp[i-1][j]<<" ";
            alz.time = max(alz.time + X*(S[i+1] - S[i]), dp[j][i+1]);
        }

        //cout<<alz.time<<"\n";
    }




    return alz.time;
}


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