fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11.  
  12. int n; 
  13. ll s, v0; 
  14.  
  15. struct Op {
  16.     ll c, v;
  17.     bool operator<(const Op& o) const {
  18.         if (c != o.c) return c < o.c;
  19.         return v > o.v;
  20.     }
  21. };
  22.  
  23. struct Line {
  24.     ll T, P, V;
  25.     pair<ll, ll> eval(ll x) const {
  26.         ll req = x - P;
  27.         if (req <= 0) return {T, -(P - x)};
  28.         ll dt = (req + V - 1) / V;
  29.         return {T + dt, -(dt * V + P - x)};
  30.     }
  31. };
  32.  
  33. bool better(Line L1, Line L2, ll x) { return L2.eval(x) < L1.eval(x); }
  34.  
  35. ll cross(Line L1, Line L2) {
  36.     ll low = 0, high = s + 1, ans = high;
  37.     while (low <= high) {
  38.         ll mid = low + (high - low) / 2;
  39.         if (better(L1, L2, mid)) ans = mid, high = mid - 1;
  40.         else low = mid + 1;
  41.     }
  42.     return ans;
  43. }
  44.  
  45. bool bad(Line L1, Line L2, Line L3) {
  46.     return cross(L2, L3) <= cross(L1, L2);
  47. }
  48.  
  49. void solve() {
  50.     cin >> n >> s >> v0;
  51.     vector<Op> ops(n);
  52.     for (int i = 0; i < n; i++) cin >> ops[i].c >> ops[i].v;
  53.     sort(ops.begin(), ops.end());
  54.     vector<Op> f;
  55.     ll max_v = v0;
  56.     for (auto op : ops)
  57.         if (chmax(max_v, op.v) && op.c < s)
  58.             f.push_back(op);
  59.     int m = f.size();
  60.     vector<Line> lines(m + 1);
  61.     lines[0] = {0, 0, v0};
  62.     deque<Line> dq;
  63.     dq.push_back(lines[0]);
  64.     for (int i = 1; i <= m; i++) {
  65.         int x = f[i - 1].c;
  66.         while ((int)dq.size() >= 2 && better(dq[0], dq[1], x)) dq.pop_front();
  67.         auto [T, P] = dq.front().eval(x);
  68.         lines[i] = {T, -P, f[i - 1].v};
  69.         while ((int)dq.size() >= 2) {
  70.             if (bad(dq[(int)dq.size() - 2], dq.back(), lines[i])) dq.pop_back();
  71.             else break;
  72.         }
  73.         dq.push_back(lines[i]);
  74.     }
  75.     while ((int)dq.size() >= 2 && better(dq[0], dq[1], s)) dq.pop_front();
  76.     cout << dq.front().eval(s).first << '\n';
  77. }
  78.  
  79. int main() {
  80.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  81.  
  82.     int tests = 1; // cin >> tests;
  83.     while (tests--) solve();
  84.  
  85.     #ifdef LOCAL
  86.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  87.     #endif
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
2 9 1
3 2
4 5
stdout
copy 
6
https://ideone.com/PlDVSN
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!