제출 #843685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
843685		bachhoangxuan	Overtaking (IOI23_overtaking)	C++17	65 / 100	3542 ms	26348 KiB

overtaking

#include "overtaking.h"

#include<bits/stdc++.h>
using namespace std;
const long long inf=LLONG_MAX;
const int maxn=1e3+5;
#define pii pair<long long,long long>
#define fi first
#define se second

struct bus{
    long long s,t;
    int id;
    bool operator<(bus o){
        if(s!=o.s) return s<o.s;
        else return t<o.t;
    }
};

int M,N;
long long X,L;
vector<long long> T,S,W;

bus B[maxn][maxn];

void init(int l, int n, vector<long long> st, vector<int> w, int x, int m, vector<int> s)
{
    L=l;N=n;X=x;M=m;T=st;
    W.resize(N);S.resize(M);
    for(int i=0;i<N;i++) W[i]=w[i];
    for(int i=0;i<M;i++) S[i]=s[i];

    for(int i=M-1;i>=1;i--) S[i]-=S[i-1];
    for(int i=0;i<N;i++) B[0][i]={0,T[i],i};
    for(int i=1;i<M;i++){
        for(int j=0;j<N;j++){
            auto [ss,tt,id]=B[i-1][j];
            B[i][j]={tt,tt+S[i]*W[id],id};
        }
        sort(B[i],B[i]+N);
        for(int j=1;j<N;j++) B[i][j].t=max(B[i][j].t,B[i][j-1].t);
    }
}

long long arrival_time(long long cur)
{
    for(int i=1;i<M;i++){
        int l=0,r=N-1,pos=-1;
        while(r>=l){
            int mid=(l+r)>>1;
            if(B[i][mid].s<cur) pos=mid,l=mid+1;
            else r=mid-1;
        }
        cur=cur+X*S[i];
        if(pos!=-1) cur=max(cur,B[i][pos].t);
    }
    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