Submission #981037

#	Time	Username	Problem	Language	Result	Execution time	Memory
981037		vjudge1	Overtaking (IOI23_overtaking)	C++17	39 / 100	3598 ms	604 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using lli=long long;
#define pb push_back
lli Nx;
lli Ti;
lli Wi;
lli Xi;
lli Lx;
lli Mx;
vector<int> st;
vector<pair<lli,lli>> val;
vector<lli> Tx;
vector<int> Wx;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    Nx=N;
    Mx=M;
    if(N==1){
    Ti=T[0];
    Wi=W[0];
    Xi=X;
    st=S;
    return;
    }
    if(M==2){
    Lx=L;
    Xi=X;
    for(int i=0; i<N; ++i){
        val.pb({T[i], W[i]});
    }
    sort(val.begin(), val.end());
    return;
    }
    Xi=X;
    st=S;
    Tx=T;
    Wx=W;
}

long long arrival_time(long long Y)
{
    if(Nx==1){
    lli M=st.size();
    vector<lli> t (M);
    vector<lli> yi (M);
    t[0]=Ti;
    yi[0]=Y;
    for(lli i=1; i<M; ++i){
        t[i]=t[i-1]+(st[i]-st[i-1])*Wi;
        yi[i]=yi[i-1]+(st[i]-st[i-1])*Xi;
        if(t[i-1]>yi[i-1]){
            if(t[i]<yi[i]){
                t[i]=yi[i];
            }
        }
        else if(t[i-1]<yi[i-1]){
            if(t[i]>yi[i]){
                yi[i]=t[i];
            }
        }
    }
    return yi[M-1];
    }
    if(Mx==2){
    lli valmax=Y+Lx*Xi;
    for(lli i=0; i<Nx; ++i){
        if(val[i].first<Y){
            valmax=max(valmax, val[i].first+Lx*val[i].second);
        }
    }
    return valmax;
    }

    vector<lli> values =Tx;
    values.pb(Y);
    priority_queue<pair<pair<lli,lli>, lli>, vector<pair<pair<lli,lli>, lli>>, greater<pair<pair<lli,lli>, lli>>> pq;
    for(lli i=0; i<Nx; ++i){
        pq.push({{values[i], Wx[i]}, i});
    }
    pq.push({{Y, Xi}, Nx});
    for(lli i=1; i<st.size(); ++i){
        lli maxi=0;
        while(!pq.empty()){
            lli a=pq.top().first.first;
            lli b=pq.top().first.second;
            lli c=pq.top().second;
            pq.pop();
            maxi=max(maxi, a+b*(st[i]-st[i-1]));
            values[c]=maxi;
           
        }
          for(lli i=0; i<Nx; ++i){
              pq.push({{values[i], Wx[i]}, i});
              }
              pq.push({{values[Nx], Xi}, Nx});
    }
    return values[Nx];


}

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:84:19: warning: comparison of integer expressions of different signedness: 'lli' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(lli i=1; i<st.size(); ++i){
      |                  ~^~~~~~~~~~

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