제출 #1127494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127494		Warinchai	추월 (IOI23_overtaking)	C++20	0 / 100	0 ms	324 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
int n,m;
int x,l;
vector<int>v;
struct line{
    long long m,b;
    line(long long _m,long long _b){
        m=_m,b=_b;
    }
    long long get(long long x){return m*x+b;}
    friend bool operator<(line a,line b){return a.m>b.m;}
};
vector<line>hull;
bool check(line a,line b,line c){
    double m1=a.m,b1=a.b,m2=b.m,b2=b.b,m3=c.m,b3=c.b;
    return (b3-b1)/(m1-m3)<(b2-b1)/(m1-m2);
}
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    n=N,m=M,x=X,v=S,l=L;
    vector<line>l;
    for(int i=0;i<N;i++)l.push_back(line(W[i],T[i]));
    sort(l.begin(),l.end());
    for(auto x:l){
        while(hull.size()>1&&check(hull[hull.size()-2],hull.back(),x))hull.pop_back();
        hull.push_back(x);
    }
    for(auto x:hull)cerr<<x.m<<" "<<x.b<<"\n";
    return;
}

long long arrival_time(long long Y)
{
    int cur=0;
    line bus=line(x,Y);
    for(int i=0;i<m;i++){
        while(cur<hull.size()-1&&hull[i].get(v[i])>=hull[i].get(v[i+1]))cur++;
        if(cur>=n)continue;
        long long val=hull[cur].get(v[i]);
        if(val<=bus.get(v[i])){
            long long dif=bus.get(v[i])-val;
            bus.b-=dif;
            cur++;
        }
    }
    return bus.get(l);
}

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