fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace __gnu_pbds;
  5. #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
  6. #define ll long long
  7. #define ld long double
  8. #define int long long
  9. #define endl "\n"
  10. #define yes cout<<"YES"<<endl;
  11. #define no cout<<"NO"<<endl;
  12. #define pb push_back
  13. using namespace std;
  14. const int MOD = 1e9 + 7;
  15. const ll INF = 1LL << 60;
  16. const int MAXN = 1e6 + 5;
  17. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
  18.  
  19. vector<ll> A, B;
  20. int N, M, K;
  21.  
  22. // Segment Tree for pair<ll, ll> {cost, flights}
  23. template<class T>
  24. struct Seg {
  25.     const T ID = {INF, INF};
  26.     ll n;
  27.     vector<T> seg;
  28.     T comb(T a, T b) {
  29.         if (a.first != b.first) return min(a, b);
  30.         return a.second < b.second ? a : b;
  31.     }
  32.     void init(ll _n) {
  33.         n = _n;
  34.         seg.assign(2 * n, ID);
  35.     }
  36.     void pull(ll p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }
  37.  
  38.     void upd(ll p, T val) {
  39.         seg[p += n] = val;
  40.         for (p /= 2; p; p /= 2) pull(p);
  41.     }
  42.  
  43.     T query(ll l, ll r) {
  44.         T ra = ID, rb = ID;
  45.         for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
  46.             if (l & 1) ra = comb(ra, seg[l++]);
  47.             if (r & 1) rb = comb(seg[--r], rb);
  48.         }
  49.         return comb(ra, rb);
  50.     }
  51. };
  52.  
  53. pair<ll, ll> work(ll lambda) {
  54.     vector<ll> dp(N + 1, INF), flight(N + 1, INF);
  55.     Seg<pair<ll, ll>> seg;
  56.     seg.init(N + 5);
  57.     dp[1] = 0;
  58.     flight[1] = 0;
  59.     seg.upd(1, {dp[1] + B[1], 0});
  60.     for (int i = 2; i <= N; i++) {
  61.         ll c1 = dp[i - 1] + A[i - 1];
  62.         ll f1 = flight[i - 1];
  63.         pair<ll, ll> aux = seg.query(max(1LL, i - K), i - 1);
  64.         ll c2 = aux.first + B[i] + lambda;
  65.         ll f2 = aux.second + 1;
  66.         if (c1 <= c2) {
  67.             dp[i] = c1;
  68.             flight[i] = f1;
  69.         } else {
  70.             dp[i] = c2;
  71.             flight[i] = f2;
  72.         }
  73.         seg.upd(i, {dp[i] + B[i], flight[i]});
  74.     }
  75.     return {dp[N], flight[N]};
  76. }
  77.  
  78. void solve() {
  79.     cin >> N >> M >> K;
  80.     A.resize(N);
  81.     B.resize(N + 1);
  82.     for (int i = 1; i <= N - 1; i++) {
  83.         cin >> A[i];
  84.     }
  85.     for (int i = 1; i <= N; i++) {
  86.         cin >> B[i];
  87.     }
  88.     if (M == 0) {
  89.         ll ans = 0;
  90.         for (int i = 1; i <= N - 1; i++) {
  91.             ans += A[i];
  92.         }
  93.         cout << ans << endl;
  94.         return;
  95.     }
  96.  
  97.     auto [c0, u0] = work(0);
  98.     if (u0 <= M) {
  99.         cout << c0 << endl;
  100.         return;
  101.     }
  102.     ll mn = 1, mx = 2e9, res = -1;
  103.     while (mn <= mx) {
  104.         ll mid = mn + (mx - mn) / 2;
  105.         auto [c, f] = work(mid);
  106.         if (f > M) {
  107.             mn = mid + 1;
  108.         }
  109.         else {
  110.             res = mid;
  111.             mx = mid - 1;
  112.         }
  113.     }
  114.     auto [c, f] = work(res);
  115.     cout << f - res * M << endl;
  116. }
  117.  
  118. signed main() {
  119.     FAST;
  120.     auto begin = std::chrono::high_resolution_clock::now();
  121. #ifndef ONLINE_JUDGE
  122.     freopen("input.txt", "r", stdin);
  123.     freopen("output.txt", "w", stdout);
  124. #endif
  125.     ll t = 1;
  126.     //cin >> t;
  127.     while (t--) solve();
  128. #ifndef ONLINE_JUDGE
  129.     auto end = std::chrono::high_resolution_clock::now();
  130.     cout << setprecision(4) << fixed;
  131.     cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count()
  132.          << " seconds" << endl;
  133. #endif
  134. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/kF1GcX
language:
C++14 (clang 8.0)
created:
7 hours 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!