제출 #1023837

#제출 시각아이디문제언어결과실행 시간메모리
1023837NValchanovGlobal Warming (CEOI18_glo)C++17
38 / 100
2063 ms4700 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; const int MAXN = 2e5 + 10; const int MAXA = 1e9 + 10; const int MAXX = 1e9 + 10; int n, x; vector < int > a; vector < int > tmp; void read() { cin >> n >> x; a.resize(n); for(int i = 0; i < n; i++) { cin >> a[i]; } } int lis(vector < int > arr) { vector < int > lissy; lissy.resize(n + 1); lissy[0] = -MAXA; lissy[1] = arr[0]; int ans = 1; for(int i = 1; i < n; i++) { int j = lower_bound(lissy.begin(), lissy.begin() + ans + 1, arr[i]) - lissy.begin(); ans = max(ans, j); lissy[j] = arr[i]; } return ans; } int solve_slow() { int ans = lis(a); for(int i = 0; i < n; i++) { tmp = a; for(int j = 0; j <= i; j++) { tmp[j] -= x; } ans = max(ans, lis(tmp)); } for(int i = n - 1; i >= 0; i--) { tmp = a; for(int j = n - 1; j >= i; j--) { tmp[j] += x; } ans = max(ans, lis(tmp)); } return ans; } void solve() { if(x == 0) cout << lis(a) << endl; else cout << solve_slow() << endl; } int main() { ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); read(); solve(); 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...