제출 #785210

#제출 시각아이디문제언어결과실행 시간메모리
785210andecaandeciGlobal Warming (CEOI18_glo)C++17
5 / 100
2063 ms23756 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, x, t[200005], ans = 0;

void solve(int l, int r, int s) {
  // cout << l << " " << r << " " << s << endl;
  map<int, int> maks;
  priority_queue<int> pq;
  set<int, greater<int>> memo;
  set<int>::iterator it;
  int cur;

  for (int i = l; i <= r; i++) {
    t[i] += s;
  }

  stack<int> st;
  int temp;
  for (int i = 1; i <= n; i++) {
    while (!st.empty()) {
      if (t[i] <= st.top()) st.pop();
      else break;
    }
    st.push(t[i]);
    // pq.push(t[i]);
    memo.insert(t[i]);
    temp = st.size();
    maks[t[i]] = max(maks[t[i]], temp);
    // int cur = pq.top();
    // pq.pop();
    // maks[t[i]] = max(maks[t[i]], maks[pq.top()]+1);
    // pq.push(cur);
    if (memo.size() > 1 and t[i] == *memo.begin()) {
      it = memo.begin();
      it++;
      cur = *it;
      maks[t[i]] = max(maks[t[i]], maks[cur]+1);
    }
    temp = maks[t[i]];
    // cout << i << " " << t[i] << " " << temp << endl;
    ans = max(temp, ans);
  }

  for (int i = l; i <= r; i++) {
    t[i] -= s;
  }
}

signed main() {
  cin >> n >> x;
  for (int i = 1; i <= n; i++) cin >> t[i];

  if (x == 0) {
    solve(1, n, 0);
    cout << ans << endl;
    return 0;
  }

  for (int l = 1; l <= n; l++) {
    for (int r = l; r <= n; r++) {
      for (int s = -x; s <= x; s++) {
        solve(l, r, s);
      }
    }
  }

  cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...