Submission #1049270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049270		AIF_is_carving	Overtaking (IOI23_overtaking)	C++17	10 / 100	2 ms	7516 KiB

overtaking

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef struct{
    ll time;
    ll skm;
    float idx;
    int 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;
}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:80:27: warning: narrowing conversion of 'N' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   80 |     zadu alz = {Y, X, NN, N};
      |                           ^

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