Submission #1063372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063372		De3b0o	Overtaking (IOI23_overtaking)	C++17	65 / 100	3563 ms	49748 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
#include<random>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#define sq 547

using namespace std;

ll n , t[1009] , w[1009] , x , m , s[1009];
ll a[1009][1009];
map<ll,vector<ll>> mp;
vector<pll> et[1009];
ll lo;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    lo=L;
    n=N;
    m=M;
    x=X;
    for(int i = 0 ; n>i ; i++)
    {
        t[i]=T[i];
        w[i]=W[i];
    }
    for(int i = 0 ; m>i ; i++)
        s[i]=S[i];
    for(int i = 0 ; n>i ; i++)
    {
        a[i][0]=t[i];
        mp[t[i]].pb(i);
    }
    ll ps = 0;
    for(int j = 1 ; m>j ; j++)
    {
        ll me = 0;
        for(auto it : mp)
        {
            ll mee = 0;
            for(auto b : it.S)
            {
                ll e = it.F+w[b]*(s[j]-ps);
                mee=max(mee,e);
                a[b][j]=max(e,me);
            }
            me=max(me,mee);
        }
        mp.clear();
        for(int i = 0 ; n>i ; i++)
            mp[a[i][j]].pb(i);
        ps=s[j];
    }
    for(int j = 0 ; m-1>j ; j++)
    {
        for(int i = 0 ; n>i ; i++)
            et[j].pb({a[i][j],a[i][j+1]});
        sort(et[j].begin(),et[j].end());
        for(int i = 1 ; n>i ; i++)
            et[j][i].S=max(et[j][i].S,et[j][i-1].S);
    }
}

long long arrival_time(long long Y)
{
    ll ans=Y;
    for(int j = 0 ; m-1>j ; j++)
    {
        ll l = 0 , r = n-1;
        ll xx = -1;
        while(l<=r)
        {
            if(et[j][mid].F>=ans)
                r=mid-1;
            else
            {
                xx=mid;
                l=mid+1;
            }
        }
        if(xx==-1)
        {
            ans+=(lo-s[j])*x;
            break;
        }
        ans=max(et[j][mid].S,ans+(s[j+1]-s[j])*x);
    }
    return ans;
}

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