Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
- using ll = long long;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- using vi = vector<int>;
- int main(int argc, char **argv)
- {
- int n, m;
- cin >> n >> m;
- vl a(n);
- for (auto &x : a)
- cin >> x;
- vl opt;
- for (int i = 0, prev = -1; i < n; ++i) {
- if (a[i] >= m) {
- if (prev != -1) {
- opt.push_back(a[prev]);
- prev = -1;
- }
- opt.push_back(a[i]);
- } else {
- if (prev == -1)
- prev = i;
- else if (a[prev] < a[i])
- prev = i;
- }
- }
- n = opt.size();
- using a2i = array<int, 2>;
- vector<a2i> dp(n + 1); // take and no take
- dp[0] = {opt[0] >= m, 0};
- for (int i = 0; i < n; ++i) {
- if (i >= 2) {
- ll sum = opt[i] + opt[i - 1] + opt[i - 2];
- if (sum >= 3 * m) {
- int md = max(dp[i - 1][0], dp[i - 1][1]);
- dp[i] = {md + 1, md};
- } else
- dp[i] = dp[i - 1];
- } else if (i >= 1) {
- ll sum = opt[i] + opt[i - 1];
- if (sum >= 2 * m) {
- int md = max(dp[i - 1][0], dp[i - 1][1]);
- dp[i] = {md + 1, md};
- } else
- dp[i] = dp[i - 1];
- }
- }
- cout << max(dp[n - 1][0], dp[n - 1][1]) << endl;
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement