제출 #1104013

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

const int N = 2e5 + 3;
int ar[N];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, x; cin >> n >> x;
  for(int i=1; i<=n; ++i) cin >> ar[i];

  if(x == 1e9) {
    vector<int> dp1(n+1), dp2(n+1);

    vector<int> lis;
    for(int i=1; i<=n; ++i) {
      auto t = lower_bound(lis.begin(), lis.end(), ar[i]);
      if(t == lis.end()) {
        lis.emplace_back(ar[i]);
      }else {
        *t = ar[i];
      }
      dp1[i] = lis.size();
    }

    lis.clear();
    for(int i=n; i>=1; --i) {
      auto t = lower_bound(lis.begin(), lis.end(), ar[i]);
      if(t == lis.end()) {
        lis.emplace_back(ar[i]);
      }else {
        *t = ar[i];
      }
      dp2[i] = lis.size();
    }

    int res = 1;
    for(int i=1; i<n; ++i) {
      res = max(res, dp1[i] + dp2[i+1]);
    }
    cout << res << '\n';
    return 0;
  }

  if(x == 0) {
    vector<int> lis;
    for(int i=1; i<=n; ++i) {
      auto t = lower_bound(lis.begin(), lis.end(), ar[i]);
      if(t == lis.end()) {
        lis.emplace_back(ar[i]);
      }else {
        *t = ar[i];
      }
    }

    cout << lis.size() << '\n';
    return 0;
  }

  int res = 0;
  for(int i=1; i<=n; ++i) {
    ar[i] -= x;

    vector<int> lis;
    for(int i=1; i<=n; ++i) {
      auto t = lower_bound(lis.begin(), lis.end(), ar[i]);
      if(t == lis.end()) {
        lis.emplace_back(ar[i]);
      }else {
        *t = ar[i];
      }
    }

    res = max(res, (int)lis.size());
  }

  cout << res << '\n';
  return 0;
}
#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...