Submission #1159934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159934		_8_8_	Overtaking (IOI23_overtaking)	C++20	0 / 100	0 ms	324 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 12;
int n,m,x;
vector<ll> t;
vector<int> w,s,ord[N];
ll e[N][N], dp[N][N];

void init(int L, int nn,vector<ll> T,vector<int> W, int X, int M,vector<int> S_) {
    for(int i = 0; i < nn; i++) {
        if(W[i] > X) {
            n++;
            t.push_back(T[i]);
            w.push_back(W[i]);
        }
    }
    s = S_;
    m = M;
    x = X;
    for(int j = 0;j < m;j++) {
        ord[j].resize(n);
        iota(ord[j].begin(),ord[j].end(),0);
    }
    for(int j = 0;j < n;j++) {
        e[0][j] = t[j];
    }
    sort(ord[0].begin(),ord[0].end(),[&](int x,int y) {
        return make_pair(e[0][x],w[x]) < make_pair(e[0][y],w[y]);
    });
    for(int i = 1;i < M;i++) {
        ll dist = s[i] - s[i - 1];
        for(int j = 0;j < n;++j) {
            int v = ord[i - 1][j];
            e[i][v] = e[i - 1][v] + dist * 1ll * w[v];
            if(j) {
                int to = ord[i - 1][j - 1];
                e[i][v] = max(e[i][v],e[i][to]);
            }
        }
        sort(ord[i].begin(),ord[i].end(),[&](int x,int y){
            return make_pair(e[i][x],w[x]) < make_pair(e[i][y],w[y]);
        });
    }
    for(int i = m - 1; i >= 0; i--) {
        dp[i][0] = e[i][0] + (s[m - 1] - s[i]) * 1ll * x;
        for(int j = 1; j < n; j++) { 
            int l = i, r = m;
            while(r - l > 1) {
                int mid = (l + r) >> 1;
                if(e[mid][ord[mid][j - 1]] >= e[i][j] + (s[mid] - s[i]) * 1ll * x) {
                    r = mid;
                } else {
                    l = mid;
                }
            }
            if(r == m) {
                dp[i][j] = e[i][j] + (s[m - 1] - s[i]) * 1ll * x;
            } else {
                dp[i][j] = dp[r][j - 1];
            }
        }
    }
    // for(int i = 0; i < m; i++) {
    //     for(int j = 0; j < n; j++) {
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
}
ll arrival_time(ll Y) {
    ll cur = Y;
    if(!n || Y < e[0][ord[0][0]]) {
        return Y + (s[m - 1] - s[0]) * 1ll * x;
    }
    auto find = [&]() {
        int l = 0, r = n;
        while(r - l > 1) {
            int mid = (l + r) >> 1;
            if(e[0][ord[0][mid]] >= Y) {
                r = mid; 
            } else {
                l = mid;
            }
        }
        return l;
    };
    int k = find();
    int l = -1, r = m;
    while(r - l > 1) {
        int mid = (l + r) >> 1;
        if(e[mid][ord[mid][k]] >= (s[mid] - s[0]) * 1ll * x + Y) {
            r = mid;
        } else {
            l = mid;
        }
    }
    // cout << l << ' ' << r << '\n';
    if(l == -1) {
        return Y + (s[m - 1] - s[0]) * 1ll * x;
    }
    return dp[l][k];
}

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