Advertisement
Korotkodul

N2_T

Nov 15th, 2022 (edited)
621
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.66 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int, int>
  11. #define pb(x) push_back(x)
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v) {
  17.     for (auto x : v) cout << x << ' ';
  18.     cout << "\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v) {
  22.     for (auto x : v) cout << x << ' ';
  23.     cout << "\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v) {
  28.     for (auto x : v) cv(x);
  29.     cout << "\n";
  30. }
  31.  
  32. void cvb(vector <bool> v) {
  33.     for (bool x : v) cout << x << ' ';
  34.     cout << "\n";
  35. }
  36.  
  37. void cvs(vector <string>  v) {
  38.     for (auto a : v) {
  39.         cout << a << "\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a) {
  44.     for (auto p : a) {
  45.         cout << p.first << ' ' << p.second << "\n";
  46.     }
  47.     cout << "\n";
  48. }
  49.  
  50. bool sh = 0;
  51. vector <ll> a, dp;
  52. int L, R;
  53. ll n, k, p;
  54. int inf = 2e9;
  55. ll N;
  56. struct tree {
  57.     vector <ll> mx;
  58.     ll bld() {
  59.         cin >> n >> k >> p;
  60.         N = log2(n + 2);
  61.         if (pow(2, N) < n + 2) N++;
  62.         N = pow(2, N);
  63.         a.resize(n + 2);
  64.         dp.assign(n + 2, -inf);
  65.         a[0] = 0;
  66.         a[n + 1] = 0;
  67.         dp[0] = p;
  68.         for (int i = 1; i <= n; ++i) {
  69.             cin >> a[i];
  70.         }
  71.         if (sh) {
  72.             cout << "n k p = " << n << ' ' << k << ' ' << p << "\n";
  73.             cout << "a\n"; cvl(a);
  74.         }
  75.         mx.assign(2 * N - 1, -inf);
  76.         mx[N - 1] = dp[0];
  77.         for (int i = N - 2; i >= 0; --i) {
  78.             mx[i] = max(mx[i * 2 + 1], mx[2 * i + 2]);
  79.         }
  80.     }
  81.     ll get(int id, int l, int r) {
  82.         if (l >= L && r <= R) {
  83.             return mx[id];
  84.         }
  85.         if (max(l, L) <= min(r, R)) {
  86.             int m = (l + r) / 2;
  87.             ll a = get(2 * id + 1, l, m);
  88.             ll b = get(2 * id + 2, m + 1, r);
  89.             return max(a, b);
  90.         }
  91.         return -inf;
  92.     }
  93.  
  94.     void upd(int id, ll x) {
  95.         id += N - 1;
  96.         mx[id] = x;
  97.         while ( (id - 1) / 2 >= 0) {
  98.             id--; id /= 2;
  99.             mx[id] = max(mx[2 * id + 1], mx[2 * id + 2]);
  100.             if (id == 0) break;
  101.         }
  102.     }
  103.  
  104.     void see() {
  105.         int id = -1;
  106.         for (int i = 0; i <= log2(N); ++i) {
  107.             for (int j = 0; j < pow(2, i); ++j) {
  108.                 id++;
  109.                 cout << mx[id] << ' ';
  110.             } cout << "\n";
  111.         } cout << "\n";
  112.     }
  113. };
  114. /*
  115. 3 1 2
  116. -2 10 100
  117. */
  118. int main() {
  119.     ios::sync_with_stdio(0);
  120.     cin.tie(0);
  121.     cout.tie(0);
  122.  
  123.     tree T;
  124.     T.bld();
  125.  
  126.     for (ll i = 1; i <= n + 1; ++i) {
  127.         if (sh) {
  128.             cout << "i = " << i << "\n";
  129.             cout << "dp\n"; cvl(dp);
  130.             cout << "i - k  = " << i - k << "\n";
  131.         }
  132.         /*for (ll j = max(0LL, i - k); j <= i - 1; ++j) {
  133.             if (sh) {
  134.                 cout << "j =  " << j << "\n";
  135.             }
  136.             if (dp[j] < 0) {
  137.                 continue;
  138.             }
  139.             dp[i] = max(dp[i], dp[j] + a[i]);
  140.         }*/
  141.         L = max(0LL, i - k);
  142.         R = i - 1;
  143.         ll gt = T.get(0, 0, N - 1);
  144.         if (sh) {
  145.             cout << "L R = " << L << ' ' << R << "\n";
  146.             cout << "gt = " << gt << "\n";
  147.         }
  148.         if (gt < 0) {
  149.             continue;
  150.         }
  151.         dp[i] = a[i] + gt;
  152.         T.upd(i, dp[i]);
  153.         if (sh) {
  154.             T.see(); cout << "\n";
  155.         }
  156.     }
  157.     if (sh) {
  158.         cout << "a\n"; cvl(a);
  159.         cout << "dp\n"; cvl(dp);
  160.     }
  161.     if (dp[n + 1] < 0 ) {
  162.         cout << -1;
  163.         exit(0);
  164.     }
  165.     cout << dp[n + 1];
  166. }
  167.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement