Submission #900127

#	Time	Username	Problem	Language	Result	Execution time	Memory
900127		Nonoze	Overtaking (IOI23_overtaking)	C++17	0 / 100	0 ms	348 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<long long, long long>>> te;
vector<vector<long long>> prefix;
vector<int> s;
long long n, m, x, l;

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
    #define int long long

    l=L, n=N, m=M, x=X, s=S;
    te.clear();
    te.resize(m, vector<pair<int, int>>(n, {0, 0}));
    prefix.clear();
    prefix.resize(m, vector<int>(n, 0));
    for (int i=0; i<n; i++) te[0][i].first=T[i];
    for (int i=1; i<m; i++) {
        vector<pair<int, int>> temp;
        for (int j=0; j<n; j++) {
            te[i-1][j].second=te[i-1][j].first+W[j]*(s[i]-s[i-1]);
            temp.push_back({te[i-1][j].first, j});
        }
        sort(temp.begin(), temp.end());
        int mx=0;
        for (int j=0; j<n; j++) {
            mx=max(mx, te[i-1][temp[j].second].second);
            te[i][temp[j].second].first=mx;
        }
    }
    for (int i=0; i<m; i++) {
        sort(te[i].begin(), te[i].end());
        prefix[i][0]=te[i][0].second;
        for (int j=1; j<n; j++) {
            prefix[i][j]=max(prefix[i][j-1], te[i][j].second);
        }
    }
    return;
}

long long arrival_time(long long y)
{
    int act=y;
    for (int i=1; i<m; i++) {
        int lb=lower_bound(te[i-1].begin(), te[i-1].end(), make_pair(act, LLONG_MIN))-te[i-1].begin();
        act=max(act+x*(s[i]-s[i-1]), (lb>0?prefix[i-1][lb-1]:0));
    }
    return act;
}

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