fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target("popcnt")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. using ll = long long;
  7.  
  8. const int MOD = 1020050909;
  9. const ll INF = 5e18;
  10. const int SIZE = 1e6 + 5;
  11. const int MAX = 1e6;
  12.  
  13. struct Line {
  14.     int m = 0;
  15.     ll k = -INF;
  16.     Line() {}
  17.     Line (int m, ll k) : m (m), k (k) {}
  18.     ll operator () (int x) {
  19.         return 1ll * m * x + k;
  20.     }
  21. };
  22.  
  23. struct Node {
  24.     Line line;
  25.     int ls, rs;
  26.     Node() {}
  27.     Node (Line line) : ls (0), rs (0), line (line) {}
  28. } node[SIZE];
  29.  
  30. int root, cnt;
  31.  
  32. int newnode (Line line) {
  33.     node[++cnt] = Node (line);
  34.     return cnt;
  35. }
  36.  
  37. void Ins (int &pos, int l, int r, Line line) {
  38.     if (pos == 0) {
  39.         pos = newnode (line);
  40.         return;
  41.     }
  42.     Node &nd = node[pos];
  43.     if (l == r) {
  44.         if (line (l) > nd.line (l)) swap (line, nd.line);
  45.         return;
  46.     }
  47.     int mid = (l + r) / 2;
  48.     if (line (mid) > nd.line (mid)) swap (line, nd.line);
  49.     if (line.m <= nd.line.m) Ins (nd.ls, l, mid, line);
  50.     else Ins (nd.rs, mid + 1, r, line);
  51. }
  52.  
  53. ll Que (int pos, int l, int r, int x) {
  54.     if (pos == 0) return -INF;
  55.     Node nd = node[pos];
  56.     if (l == r) return nd.line (x);
  57.     int mid = (l + r) / 2;
  58.     return max (nd.line (x), x <= mid ? Que (nd.ls, l, mid, x) : Que (nd.rs, mid + 1, r, x));
  59. }
  60.  
  61. int n, k;
  62. ll ans, dp[SIZE];
  63. vector<int> L[SIZE], R[SIZE];
  64. int a[SIZE], b[SIZE], m[SIZE];
  65.  
  66. int main() {
  67.     ios::sync_with_stdio (false), cin.tie (0);
  68.     cin >> n >> k;
  69.     for (int i = 0; i <= n; i++) cin >> a[i];
  70.     for (int i = 1; i <= n; i++) cin >> b[i];
  71.     for (int i = 1; i <= n; i++) cin >> m[i];
  72.     for (int i = 1; i <= n; i++) {
  73.         int l = max (0, b[i] - k + 1), r = b[i];
  74.         L[l].emplace_back (i);
  75.         R[r].emplace_back (i);
  76.         dp[i] = -INF;
  77.     }
  78.     for (int i = 0; i <= n; i++) {
  79.         if (i % k == 0) {
  80.             int l = max (0, i - k + 1), r = i;
  81.             root = cnt = 0;
  82.             while (r >= l) {
  83.                 Ins (root, 0, MAX, Line (-a[r], dp[r]));
  84.                 for (int pos : L[r]) {
  85.                     dp[pos] = max (dp[pos], Que (root, 0, MAX, m[pos]) + 1ll * m[pos] * (a[pos] + 1));
  86.                 }
  87.                 r--;
  88.             }
  89.             root = cnt = 0;
  90.         }
  91.         Ins (root, 0, MAX, Line (-a[i], dp[i]));
  92.         for (int pos : R[i]) {
  93.             dp[pos] = max (dp[pos], Que (root, 0, MAX, m[pos]) + 1ll * m[pos] * (a[pos] + 1));
  94.         }
  95.         ans += dp[i] % MOD;
  96.     }
  97.     cout << ans % MOD << '\n';
  98. }
Runtime error #stdin #stdout 0.03s 74020KB
comments (?)
stdin
copy 
PCCORZ
stdout
copy 
Standard output is empty
https://ideone.com/wlbjLG
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!