Advertisement
SorahISA

IOIC '22 p52. 序列分割

Jan 26th, 2022
950
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2.  
  3. /// Fast I/O by FHVirus ///
  4. /// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
  5.  
  6. #include <unistd.h>
  7.  
  8. const int S = 65536;
  9.  
  10. int OP = 0;
  11. char OB[S];
  12.  
  13. inline char RC() {
  14.     static char buf[S], *p = buf, *q = buf;
  15.     return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
  16. }
  17.  
  18. inline int RI() {
  19.     static char c;
  20.     int a;
  21.     while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
  22.     if (c == '-') {
  23.         a = 0;
  24.         while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
  25.     }
  26.     else {
  27.         a = c ^ '0';
  28.         while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
  29.     }
  30.     return a;
  31. }
  32.  
  33. /// Fast I/O by FHVirus ///
  34. /// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///
  35.  
  36. #define int long long
  37.  
  38. const int INF = 1E17;
  39.  
  40. struct Line {
  41.     int a, b, id; /// ax+b
  42.     Line(int _a = 0, int _b = 0, int _id = 0) : a(_a), b(_b), id(_id) {}
  43.     int val(int x) {return a*x + b;}
  44. };
  45.  
  46. inline bool check(Line l1, Line l2, Line l3, int x) {
  47.     return (((l3.a - l2.a) * (l1.b - l2.b) >= (l3.b - l2.b) * (l1.a - l2.a))
  48.         and (l2.b - l3.b < x * (l3.a - l2.a)));
  49. }
  50.  
  51. signed main() {
  52.     /// dp[i] = a[i] + b*i*i + max(dp[j] + b*j*j + 2*b*j*i) ///
  53.     /// dp[0] = a[0] ///
  54.     /// transfer from j which max(i-K, 0) <= j < i ///
  55.    
  56.     int N = RI(), K = RI(), B = RI();
  57.    
  58.     int A[N];
  59.     for (int &x : A) x = RI();
  60.    
  61.     int dp[N];
  62.     for (int i = 1; i < N; ++i) dp[i] = -INF;
  63.     dp[0] = A[0];
  64.    
  65.     int fr = 0, bk = 0;
  66.     Line deq[N];
  67.     deq[bk++] = Line(0, dp[0], 0);
  68.     for (int i = 1; i < N; ++i) {
  69.         if (deq[fr].id < i-K) ++fr;
  70.         while (bk - fr >= 2 and deq[fr].val(i) < deq[fr+1].val(i)) ++fr;
  71.         dp[i] = deq[fr].val(i) + A[i] - B*i*i;
  72.         Line l(2*B*i, dp[i] - B*i*i, i);
  73.         while (bk - fr >= 2 and check(deq[bk-2], deq[bk-1], l, i+K-1)) --bk;
  74.         deq[bk++] = l;
  75.     }
  76.    
  77.     printf("%lld\n", dp[N-1]);
  78. }
  79.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement