Submission #1127494

#TimeUsernameProblemLanguageResultExecution timeMemory
1127494WarinchaiOvertaking (IOI23_overtaking)C++20
0 / 100
0 ms324 KiB
#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); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...