fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define Waimai ios::sync_with_stdio(false),cin.tie(0)
  7. #define FOR(x,a,b) for (int x=a;x<=b;x++)
  8. #define pb emplace_back
  9. #define F first
  10. #define S second
  11.  
  12. const int SIZE = 1e6 + 5;
  13. const __int128 INF = 1e18;
  14. const double dINF = log ((ll) INF);
  15.  
  16. struct Seg {int pos, l, r;};
  17.  
  18. int n, k, p;
  19. int L[SIZE];
  20. ll pre[SIZE], dp[SIZE];
  21. Seg st[SIZE];
  22. int sl = 1, sr;
  23.  
  24. ll power (ll d, int up) {
  25.     ll ans = 1;
  26.     while (up) {
  27.         if (up & 1) ans = min (INF, (__int128) ans * d);
  28.         d = min (INF, (__int128) d * d);
  29.         up >>= 1;
  30.     }
  31.     return ans;
  32. }
  33.  
  34. double power (double d, int up) {
  35.     double ans = 1;
  36.     while (up) {
  37.         if (up & 1) ans *= d;
  38.         d *= d;
  39.         up >>= 1;
  40.     }
  41.     return ans;
  42. }
  43.  
  44. ll cal (int l, int r) {
  45.     return dp[l] + power (abs (pre[r] - pre[l] - L[r] - k), p);
  46. }
  47.  
  48. bool better (int x, int y, int r) {
  49.     ll t1 = abs (pre[r] - pre[x] - L[r] - k), t2 = abs (pre[r] - pre[y] - L[r] - k);
  50.     if (dp[x] <= dp[y] && t1 <= t2) return 1;
  51.     if (dp[x] >= dp[y] && t1 >= t2) return 0;
  52.     return dp[x] + power (1.00 * t1, p) <= dp[y] + power (1.00 * t2, p);
  53. }
  54.  
  55. void solve() {
  56.     cin >> n >> k >> p;
  57.     FOR (i, 1, n) cin >> pre[i];
  58.     for (int i = 1; i < n; i++) {
  59.         cin >> L[i];
  60.         pre[i] += pre[i - 1] + L[i];
  61.     }
  62.     pre[n] += pre[n - 1];
  63.     st[++sr] = {0, 1, n};
  64.     FOR (i, 1, n) {
  65.         dp[i] = cal (st[sl].pos, i);
  66.         if (st[sl].l == i) {
  67.             if (st[sl].l == st[sl].r) sl++;
  68.             else st[sl].l++;
  69.         }
  70.         while (sl <= sr && better (i, st[sr].pos, st[sr].l)) sr--;
  71.         if (sl > sr) st[++sr] = {i, i + 1, n};
  72.         else if (!better (i, st[sr].pos, st[sr].r)) {
  73.             if (st[sr].r != n) {
  74.                 st[++sr] = {i, st[sr - 1].r + 1, n};
  75.             }
  76.         } else {
  77.             auto [pos, l, r] = st[sr];
  78.             while (l < r) {
  79.                 int mid = (l + r) / 2;
  80.                 if (better (i, pos, mid)) r = mid;
  81.                 else l = mid + 1;
  82.             }
  83.             st[sr].r = l - 1;
  84.             st[++sr] = {i, l, n};
  85.         }
  86.     }
  87.     cout << dp[n] << '\n';
  88. }
  89.  
  90. int main() {
  91.     Waimai;
  92.     solve();
  93. }
Success #stdin #stdout 0.01s 5604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/mw9f18
language:
C++14 (gcc 8.3)
created:
2 years 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!