Submission #1089725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089725		lighton	Overtaking (IOI23_overtaking)	C++17	65 / 100	3539 ms	79252 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
vector<vector<ll> > state;
vector<vector<ll> > dp;
vector<vector<vector<ll> > > num;
vector<vector<ll> > h;
vector<ll> vel,st;
vector<int> s;
ll add;
double cross(ll a1, ll b1 , ll a2, ll b2){
    return (double)(b2-b1)/(double)(a1-a2);
}
int n,m;

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    s=S;
    forf(i,0,N-1) if(W[i]-X > 0) vel.pb(W[i]-X), st.pb(T[i]);
    add = ((ll)X)*L;

    m = s.size();
    n = vel.size();
    state.resize(m,{}),dp.resize(m,{}),num.resize(m,{});
    h.resize(n,vector<ll>(m,0));
    {
        forf(i, 0, n - 1) h[i][0] = st[i];
        forf(i, 0, n - 1) state[0].pb(h[i][0]);
        sort(all(state[0])), comp(state[0]);
        dp[0].resize(state[0].size()), num[0].resize(state[0].size());
        forf(i, 0, n - 1) num[0][idx(h[i][0], state[0])].pb(i);

        forf(i, 0, m - 2) {
            ll pmx = 0;
            ll delta = s[i + 1] - s[i];
            forf(j, 0, (int) state[i].size() - 1) {
                ll now = state[i][j];
                ll tmp = 0;
                for (int idx: num[i][j]) {
                    ll nxt = max(now + delta * vel[idx], pmx);
                    tmp = max(nxt,tmp);
                    h[idx][i + 1] = nxt;
                    state[i + 1].pb(nxt);
                }
                pmx = max(pmx, tmp);
                dp[i][j] = pmx;
            }

            sort(all(state[i + 1])), comp(state[i + 1]);
            int sz = state[i + 1].size();
            dp[i + 1].resize(sz), num[i + 1].resize(sz);
            forf(j, 0, n - 1) num[i + 1][idx(h[j][i + 1], state[i + 1])].pb(j);
        }
    }
}

long long arrival_time(long long Y)
{
    ll now = Y;
    forf(i,0,m-2){
        int j = lower_bound(all(state[i]),now)-state[i].begin()-1;
        if(j != -1) now = max(now, dp[i][j]);
    }
    return now+add;
}

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