Submission #843217

#	Time	Username	Problem	Language	Result	Execution time	Memory
843217		yutabi	Overtaking (IOI23_overtaking)	C++17	100 / 100	530 ms	53692 KiB

overtaking

#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
    
    
    
typedef long long ll;
typedef pair <ll,int> bus;
    
    
    
bus busses[1001][1001];
    
ll stuck[1001][1001];
    
int n;
int m;
    
vector <int> s;
    
int x;

bool yolo;
    
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;
    s=S;
    x=X;
    
    for(int i=0;i<M;i++)
    {
        multiset <bus> st;
        
        if(i==0)
        {
            int skipped=0;
    
            for(int j=0;j<N;j++)
            {
                if(W[j]<=X)
                {
                    skipped++;
    
                    continue;
                }
    
                st.insert({T[j],W[j]});
            }
    
            N-=skipped;
            n-=skipped;

            if(N==0)
            {
                yolo=true;
                return;
            }
    
            for(int j=0;j<N;j++)
            {
                if(st.empty())
                {
                    assert(0);
                }

                busses[0][j]=*(st.begin());
                st.erase(st.begin());
            }
    
            continue;
        }
    
        ll maxi=-1;
    
        for(int j=0;j<N;j++)
        {
            bus curr=busses[i-1][j];
            
            curr.first+=((ll)(S[i]-S[i-1]))*curr.second;
    
            if(curr.first>maxi)
            {
                maxi=curr.first;
            }
    
            else
            {
                curr.first=maxi;
            }
            
            st.insert(curr);
        }
        
        for(int j=0;j<N;j++)
        {
            busses[i][j]=*st.begin();
            st.erase(st.begin());
        }
    }
    
    /*for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            printf("%lld %d ",busses[i][j].time,busses[i][j].speed);
        }
    
        printf("\n");
    }*/
    
    for(int i=M-1;i>0;i--)
    {
        for(int j=0;j<N;j++)
        {
            ll curr=busses[i][j].first;
    
            if(i==M-1)
            {
                stuck[i][j]=curr;
    
                continue;
            }
    
            if(j==0)
            {
                stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X;
    
                continue;
            }
    
            if(j>0 && busses[i][j].first==busses[i][j-1].first)
            {
                stuck[i][j]=stuck[i][j-1];
    
                continue;
            }
    
            int curr_loc=i;
    
            for(int k=9;k>=0;k--)
            {
                int next_loc=curr_loc+(1<<k);
                next_loc=min(next_loc,M-1);
    
                ll nxt=curr;
    
                nxt+=((ll)(S[next_loc]-S[i]))*X;
    
                if(nxt>busses[next_loc][j-1].first)
                {
                    curr_loc=next_loc;
                }
            }
    
            curr_loc++;
    
            if(curr_loc==M)
            {
                stuck[i][j]=curr+((ll)(S[M-1]-S[i]))*X;
    
                continue;
            }
    
            stuck[i][j]=stuck[curr_loc][j-1];
        }
    }
    
    /*for(int i=1;i<M;i++)
    {
        for(int j=0;j<N;j++)
        {
            printf("%lld ",stuck[i][j]);
        }
    
        printf("\n");
    }*/
    
    return;
}
    
long long arrival_time(long long Y)
{
    if(yolo)
    {
        return Y+((ll)(s[m-1]-s[0]))*x;
    }

    int j=n;
    
    for(int k=9;k>=0;k--)
    {
        int next_j=max(0,j-(1<<k));
    
    
    
        if(Y<=busses[0][next_j].first)
        {
            j=next_j;
        }
    }
    
    j--;
    
    if(j==-1)
    {
        return Y+((ll)(s[m-1]-s[0]))*x;
    }
    
    int curr=0;
    
    for(int k=9;k>=0;k--)
    {
        int nxt=min(curr+(1<<k),m-1);
    
        ll t=Y+((ll)(s[nxt]-s[0]))*x;
    
        if(t>busses[nxt][j].first)
        {
            curr=nxt;
        }
    }
    
    curr++;
    
    if(curr==m)
    {
        return Y+((ll)(s[m-1]-s[0]))*x;
    }
    
    return stuck[curr][j];
}

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