Submission #912780

#	Time	Username	Problem	Language	Result	Execution time	Memory
912780		Nonoze	추월 (IOI23_overtaking)	C++17	65 / 100	3520 ms	33364 KiB

overtaking

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

vector<vector<long long>> t;
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;
    t.clear();
    t.resize(m, vector<int>(n, 0));
    for (int i=0; i<n; i++) t[0][i]=T[i];
    for (int i=1; i<m; i++) {
        vector<pair<pair<int, int>, int>> temp;
        for (int j=0; j<n; j++) {
            temp.push_back({{t[i-1][j], t[i-1][j]+(W[j]*((int)(s[i]-s[i-1])))}, j});
        }
        sort(temp.begin(), temp.end());
        int mx=0;
        for (int j=0; j<n; j++) {
            mx=max(mx, temp[j].first.second);
            t[i][temp[j].second]=mx;
        }
    }
    for (int i=0; i<m; i++) sort(t[i].begin(), t[i].end());
    return;
}

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

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