Advertisement
Korotkodul

N2_T_1

Nov 15th, 2022
707
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.68 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.     void 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.  
  72.         if (sh) {
  73.             cout << "n k p = " << n << ' ' << k << ' ' << p << "\n";
  74.             cout << "a\n"; cvl(a);
  75.         }
  76.  
  77.         mx.assign(2 * N - 1, -inf);
  78.         mx[N - 1] = dp[0];
  79.         for (int i = N - 2; i >= 0; --i) {
  80.             mx[i] = max(mx[i * 2 + 1], mx[2 * i + 2]);
  81.         }
  82.     }
  83.  
  84.     ll get(int id, int l, int r) {
  85.         if (l >= L && r <= R) {
  86.             return mx[id];
  87.         }
  88.         if (max(l, L) <= min(r, R)) {
  89.             int m = (l + r) / 2;
  90.             ll a = get(2 * id + 1, l, m);
  91.             ll b = get(2 * id + 2, m + 1, r);
  92.             return max(a, b);
  93.         }
  94.         return -inf;
  95.     }
  96.  
  97.     void upd(int id, ll x) {
  98.         id += N - 1;
  99.         mx[id] = x;
  100.         while ( (id - 1) / 2 >= 0) {
  101.             id--; id /= 2;
  102.             mx[id] = max(mx[2 * id + 1], mx[2 * id + 2]);
  103.             if (id == 0) break;
  104.         }
  105.     }
  106.  
  107.     void see() {
  108.         int id = -1;
  109.         for (int i = 0; i <= log2(N); ++i) {
  110.             for (int j = 0; j < pow(2, i); ++j) {
  111.                 id++;
  112.                 cout << mx[id] << ' ';
  113.             } cout << "\n";
  114.         } cout << "\n";
  115.     }
  116. };
  117. /*
  118. 3 1 2
  119. -2 10 100
  120. */
  121. int main() {
  122.     ios::sync_with_stdio(0);
  123.     cin.tie(0);
  124.     cout.tie(0);
  125.     int wsasxa;
  126.     tree T;
  127.     T.bld();
  128.  
  129.     for (ll i = 1; i <= n + 1; ++i) {
  130.         if (sh) {
  131.             cout << "i = " << i << "\n";
  132.             cout << "dp\n"; cvl(dp);
  133.             cout << "i - k  = " << i - k << "\n";
  134.         }
  135.         /*for (ll j = max(0LL, i - k); j <= i - 1; ++j) {
  136.             if (sh) {
  137.                 cout << "j =  " << j << "\n";
  138.             }
  139.             if (dp[j] < 0) {
  140.                 continue;
  141.             }
  142.             dp[i] = max(dp[i], dp[j] + a[i]);
  143.         }*/
  144.         L = max(0LL, i - k);
  145.         R = i - 1;
  146.         ll gt = T.get(0, 0, N - 1);
  147.         if (sh) {
  148.             cout << "L R = " << L << ' ' << R << "\n";
  149.             cout << "gt = " << gt << "\n";
  150.         }
  151.         if (gt < 0) {
  152.             continue;
  153.         }
  154.         dp[i] = a[i] + gt;
  155.         T.upd(i, dp[i]);
  156.         if (sh) {
  157.             T.see(); cout << "\n";
  158.         }
  159.     }
  160.     if (sh) {
  161.         cout << "a\n"; cvl(a);
  162.         cout << "dp\n"; cvl(dp);
  163.     }
  164.     if (dp[n + 1] < 0 ) {
  165.         cout << -1;
  166.         exit(0);
  167.     }
  168.     cout << dp[n + 1];
  169. }
  170.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement