Advertisement
pb_jiang

test

Nov 25th, 2023
594
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #ifndef __DEBUG__
  5. #define dbg(...) 42
  6. #endif
  7. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. using pll = pair<ll, ll>;
  12. using vl = vector<ll>;
  13. using vi = vector<int>;
  14.  
  15. int main(int argc, char **argv)
  16. {
  17.     int n, m;
  18.     cin >> n >> m;
  19.     vl a(n);
  20.     for (auto &x : a)
  21.         cin >> x;
  22.  
  23.     vl opt;
  24.     for (int i = 0, prev = -1; i < n; ++i) {
  25.         if (a[i] >= m) {
  26.             if (prev != -1) {
  27.                 opt.push_back(a[prev]);
  28.                 prev = -1;
  29.             }
  30.             opt.push_back(a[i]);
  31.         } else {
  32.             if (prev == -1)
  33.                 prev = i;
  34.             else if (a[prev] < a[i])
  35.                 prev = i;
  36.         }
  37.     }
  38.     n = opt.size();
  39.     using a2i = array<int, 2>;
  40.     vector<a2i> dp(n + 1); // take and no take
  41.     dp[0] = {opt[0] >= m, 0};
  42.     for (int i = 0; i < n; ++i) {
  43.         if (i >= 2) {
  44.             ll sum = opt[i] + opt[i - 1] + opt[i - 2];
  45.             if (sum >= 3 * m) {
  46.                 int md = max(dp[i - 1][0], dp[i - 1][1]);
  47.                 dp[i] = {md + 1, md};
  48.             } else
  49.                 dp[i] = dp[i - 1];
  50.         } else if (i >= 1) {
  51.             ll sum = opt[i] + opt[i - 1];
  52.             if (sum >= 2 * m) {
  53.                 int md = max(dp[i - 1][0], dp[i - 1][1]);
  54.                 dp[i] = {md + 1, md};
  55.             } else
  56.                 dp[i] = dp[i - 1];
  57.         }
  58.     }
  59.     cout << max(dp[n - 1][0], dp[n - 1][1]) << endl;
  60.     return 0;
  61. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement