제출 #637612

#제출 시각아이디문제언어결과실행 시간메모리
637612stoyan_malininLong Distance Coach (JOI17_coach)C++14
100 / 100
145 ms25076 KiB
#include <algorithm> #include <iostream> #include <vector> #include <cmath> #include <set> using namespace std; const int MAXN = 2e5; const int64_t inf = 1e18; const int64_t MAXX = 1e12; struct Line { int64_t a, b; Line(){} Line(double a, double b) { this->a = a; this->b = b; } int64_t get(int64_t x) { return a*x + b; } }; double intersect(const Line &A, const Line &B) { return double(B.b-A.b)/double(A.a-B.a); } struct ConvexHullTrick { vector <Line> v; vector <double> to; void add(const Line &l) { while(v.size()>=2 && to.back()>=intersect(v[v.size()-2], l)) { v.pop_back(); to.pop_back(); } if(v.empty()==true) { v.push_back(l); } else { to.push_back(intersect(v.back(), l)); v.push_back(l); } } int64_t get(double x) { auto it = upper_bound(to.begin(), to.end(), x); return v[it-to.begin()].get(x); } }; struct Passanger { int64_t d, c; Passanger(){} Passanger(int64_t d, int64_t c) : d(d), c(c) {} }; int64_t X, n, m, W, T; int64_t sources[MAXN+5]; Passanger passangers[MAXN+5]; Passanger passangersPref[MAXN+5]; int64_t depart[MAXN+5]; int64_t endWaterPoints[MAXN+5]; int64_t endWaterPointsPrefix[MAXN+5]; int findLastPassangerBefore(int64_t rem) { int l = 0, r = m - 1, mid; while(l+1<r) { mid = (l+r)/2; if(passangers[mid].d<rem) l = mid; else r = mid - 1; } if(passangers[r].d<rem) return r; if(passangers[l].d<rem) return l; return -1; } void init() { sort(sources, sources+n); sort(passangers, passangers+m, [](const Passanger& A, const Passanger& B) { if(A.d!=B.d) return A.d<B.d; return A.c<B.c; }); for(int i = 0;i<m;i++) depart[i] = -1; for(int i = 0;i<n;i++) { int ind = findLastPassangerBefore(sources[i]%T); if(ind!=-1 && depart[ind]==-1) depart[ind] = sources[i]; } { int ind = findLastPassangerBefore(X%T); if(ind!=-1 && depart[ind]==-1) depart[ind] = X; } } int64_t dp[MAXN+5]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> X >> n >> m >> W >> T; for(int i = 0;i<n;i++) cin >> sources[i]; for(int i = 0;i<m;i++) cin >> passangers[i].d >> passangers[i].c; init(); int64_t driverWater = X/T + 1; int64_t endWaterPointsSum = 0; for(int i = 0;i<m;i++) { endWaterPoints[i] = ((X-passangers[i].d+(T-1))/T)*T + passangers[i].d; endWaterPointsSum += endWaterPoints[i]; endWaterPointsPrefix[i] = endWaterPoints[i]; if(i!=0) endWaterPointsPrefix[i] += endWaterPointsPrefix[i-1]; } int64_t beginWaterPointsSum = 0; for(int i = 0;i<m;i++) beginWaterPointsSum += passangers[i].d; passangersPref[0] = passangers[0]; for(int i = 1;i<m;i++) { passangersPref[i].d = passangersPref[i-1].d + passangers[i].d; passangersPref[i].c = passangersPref[i-1].c + passangers[i].c; } ConvexHullTrick cht; for(int i = 0;i<m;i++) { dp[i] = inf; if(i!=0) dp[i] = dp[i-1]; else dp[i] = 0; { int64_t lastDp = ((i==0)?0:dp[i-1]); int64_t lastEWPP = ((i==0)?0:endWaterPointsPrefix[i-1]); int64_t lastC = ((i==0)?0:passangersPref[i-1].c); int64_t lastD = ((i==0)?0:passangersPref[i-1].d); cht.add(Line(W*(-i), lastDp - lastC + ((-lastD + lastEWPP)/T)*W)); } if(depart[i]!=-1) { int64_t based = (depart[i]/T)*T; int64_t basedDiv = depart[i]/T; int64_t val1 = ((passangersPref[i].d - endWaterPointsPrefix[i])/T)*W + basedDiv*(i+1)*W + passangersPref[i].c; int64_t val2 = cht.get(basedDiv); dp[i] = min(dp[i], val1 + val2); } } int64_t ans = dp[m-1] + ((endWaterPointsSum-beginWaterPointsSum)/T)*W + driverWater*W; cout << ans << '\n'; } /* 19 1 4 8 7 10 1 20 2 10 4 5 6 5 */

컴파일 시 표준 에러 (stderr) 메시지

coach.cpp: In function 'int main()':
coach.cpp:175:21: warning: unused variable 'based' [-Wunused-variable]
  175 |             int64_t based = (depart[i]/T)*T;
      |                     ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...