Submission #1233831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233831		Muhammad_Aneeq	Overtaking (IOI23_overtaking)	C++17	65 / 100	3576 ms	47912 KiB

overtaking

#include "overtaking.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
int const NM=1e3+10;
long long arr[NM][NM]={};
vector<ll>tms[NM]={},pre[NM]={};
vector<int>s;
int n,m;
int x;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    x=X;
    s=S;
    n=N,m=M;
    for (int i=0;i<N;i++)
        arr[i][0]=T[i];
    for (int i=1;i<M;i++)
    {
        vector<pair<ll,int>>tm;
        for (int j=0;j<n;j++)
            tm.push_back({arr[j][i-1],j});
        pre[i-1].push_back(0);
        sort(begin(tm),end(tm));
        ll mx=0;
        for (int j=0;j<n;j++)
        {
            int k=j;
            vector<int>ind;
            while (k<n&&tm[k].first==tm[j].first)
            {
                tms[i-1].push_back(tm[k].first);
                ind.push_back(tm[k].second);
                k++;
            }
            j=k-1;
            for (auto l:ind)
                arr[l][i]=max(arr[l][i-1]+1ll*(S[i]-S[i-1])*W[l],mx);
            for (auto l:ind)
                mx=max(mx,arr[l][i]);
            for (auto l:ind)
                pre[i-1].push_back(mx);
        }
    }
    return;
}

long long arrival_time(long long Y)
{
    ll pr=Y;
    for (int i=0;i+1<m;i++)
    {
        int z=lower_bound(begin(tms[i]),end(tms[i]),pr)-begin(tms[i]);
        pr=max(pr+1ll*(s[i+1]-s[i])*x,pre[i][z]);
    }
    return pr;
}

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