제출 #1112526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112526		jerzyk	추월 (IOI23_overtaking)	C++17	65 / 100	3561 ms	26828 KiB

overtaking

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1'007;
int n, m, V;
ll dis[N], vel[N];
vector<pair<ll, int>> sta[N];
vector<ll> blo[N];

void DoSta()
{
    for(int i = 1; i < m; ++i)
    {
        sort(sta[i].begin(), sta[i].end());
        ll curma = 0LL, am = 0LL;
        for(int j = 0; j < n; ++j)
        {
            ll na = sta[i][j].st + (dis[i + 1] - dis[i]) * vel[sta[i][j].nd];
            na = max(na, curma);
            sta[i + 1].pb(make_pair(na, sta[i][j].nd));
            am = max(na, am);
            if(j == n - 1 || sta[i][j].st != sta[i][j + 1].st)
                curma = max(curma, am);
            blo[i].pb(curma);
            //cout << i << " Sta " << sta[i][j].nd << " " << sta[i][j].st << " " << na << "\n";
        }
    }
}

void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S)
{
    n = _N; m = _M; V = _X;
    for(int i = 1; i <= m; ++i)
        dis[i] = _S[i - 1];
    for(int i = 1; i <= n; ++i)
    {
        vel[i] = _W[i - 1];
        sta[1].pb(make_pair(_T[i - 1], i));
    }
    DoSta();
}

long long arrival_time(ll _Y)
{
    ll cur = _Y;
    for(int i = 1; i < m; ++i)
    {
        int j = (lower_bound(sta[i].begin(), sta[i].end(), make_pair(cur, 0)) - sta[i].begin()) - 1;
        ll nxt = cur + (dis[i + 1] - dis[i]) * V;
        if(j >= 0)
            nxt = max(nxt, blo[i][j]);
        //cerr << i << " " << cur << " " << nxt << "\n";
        cur = nxt;
    }
    return cur;
}

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