제출 #900084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900084		Ludissey	추월 (IOI23_overtaking)	C++17	39 / 100	3539 ms	19996 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int l,n,x,m;
vector<vector<pair<int,int>>> t;
vector<int> s,w;

void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed X, signed M, std::vector<signed> S)
{
    l=L;
    n=N;
    x=X;
    m=M; 
    s.assign(S.begin(),S.end());
    w.assign(W.begin(),W.end());
    t.resize(m,vector<pair<int,int>>(n));
    for (int i = 0; i < n; i++) t[0][i].first=T[i];
    for (int i = 1; i < m; i++)
    {
        int dist=s[i]-s[i-1];
        vector<int> e(n);
        for (int j = 0; j < n; j++) e[j]=t[i-1][j].first+(w[j]*dist);
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
                if(j==k) continue;
                if(t[i-1][k].first<t[i-1][j].first){
                    e[j]=max(e[j],e[k]);
                }
            }
        }
        for (int k = 0; k <= n; k++) t[i][k].first=e[k];
    }
    for (int i = 0; i < m-1; i++) for (int j = 0; j < n; j++) t[i][j].second=t[i+1][j].first;
    for (int i = 0; i < m; i++) sort(t[i].begin(),t[i].end());
    return;
}

int lb(int i, int y){
    int _l=0, _r=n-1;
    int ans=-1;
    while(_l<=_r){
        int mid=_l+(_r-_l)/2;
        if(t[i][mid].first<y) {
            _l=mid+1;
            ans=mid;
        }
        else _r=mid-1;
    }
    return ans;
}

long long arrival_time(long long Y) 
{
    for (int i = 1; i < m; i++)
    {
        int eY=Y+(x*(s[i]-s[i-1]));
        int pos=lb(i-1,Y);
        if(pos==-1) return Y+(x*(l-s[i-1]));
        Y=max(eY,t[i][pos].first);
        cerr << Y << "\n";
    }
    return Y;
}

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