Submission #1068166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068166		parsadox2	Overtaking (IOI23_overtaking)	C++17	100 / 100	906 ms	63080 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int n , tmp_cmp , m , x , len;
long long dp[N][N];
long long tim[N][N];
vector <int> w , ord[N] , s;
vector <long long> t;

bool cmp(int aa , int bb)
{
    if(tim[aa][tmp_cmp] != tim[bb][tmp_cmp])
        return tim[aa][tmp_cmp] < tim[bb][tmp_cmp];
    return w[aa] < w[bb];
}

void Sort(int id)
{
    tmp_cmp = id;
    sort(ord[id].begin() , ord[id].end() , cmp);
}

long long Solve(long long val , int id)
{
    if(id == m - 1)
        return val;
    int low = -1 , high = n;
    while(high - low > 1)
    {
        int mid = (low + high) >> 1;
        if(tim[ord[id][mid]][id] < val)
            low = mid;
        else
            high = mid;
    }
    if(low == -1)
        return val + 1LL * (len - s[id]) * x;
    int l = id , r = m;
    while(r - l > 1)
    {
        int mid = (l + r) >> 1;
        if(tim[ord[mid][low]][mid] >= val + 1LL * x * (s[mid] - s[id]))
            r = mid;
        else
            l = mid;
    }
    if(r == m)
        return val + 1LL * (len - s[id]) * x;
    return dp[ord[r][low]][r];
}

void init(int L, int nn, vector<long long> T, vector<int> W, int X, int mm, vector<int> S)
{
    vector <int> tmp;
    s = S;
    m = mm;
    x = X;
    len = L;
    for(int i = 0 ; i < nn ; i++)  if(W[i] > X)
    {
        w.push_back(W[i]);
        t.push_back(T[i]);
    }
    n = t.size();
    for(int i = 0 ; i < n ; i++)
    {
        ord[0].push_back(i);
        tim[i][0] = t[i];
    }
    Sort(0);
    for(int j = 1 ; j < m ; j++)
    {
        for(int i = 0 ; i < n ; i++)
            tim[i][j] = tim[i][j - 1] + 1LL * w[i] * (S[j] - S[j - 1]);
        ord[j] = ord[j - 1];
        for(int i = 1 ; i < n ; i++)
            tim[ord[j][i]][j] = max(tim[ord[j][i]][j] , tim[ord[j][i - 1]][j]);
        Sort(j);
    }
    for(int j = m - 1 ; j >= 0 ; j--)
    {
        for(int i = 0 ; i < n ; i++)
            dp[i][j] = Solve(tim[i][j] , j);
    }
    return;
}

long long arrival_time(long long Y)
{
    return Solve(Y , 0);
}

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