Submission #1263292

#TimeUsernameProblemLanguageResultExecution timeMemory
1263292kaloyanGlobal Warming (CEOI18_glo)C++20
28 / 100
2095 ms4932 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 2e5 + 10; const int INF = 1e18; int n, x; int a[MAXN], temp[MAXN], dp[MAXN]; int best = 0; int lower_binary(int x) { int l = -1, r = n; while(r > l + 1) { int m = (l + r) / 2; if(dp[m] >= x) { r = m; } else { l = m; } } return r; } int lis(int r, int x) { int ret = 0; for(int i = 0 ; i < n ; ++i) { temp[i] = a[i]; } for(int i = 0 ; i <= r; ++i) { temp[i] += x; } dp[0] = -INF; for(int i = 1 ; i <= n ; ++i) { dp[i] = INF; } for(int i = 0 ; i < n ; ++i) { int idx = lower_binary(temp[i]); dp[idx] = temp[i]; ret = max(ret, idx); } return ret; } void solve() { cin >> n >> x; for(int i = 0 ; i < n ; ++i) { cin >> a[i]; } for(int r = 0 ; r < n ; ++r) { best = max(best, lis(r, -x)); } cout << best << "\n"; } void fastIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } signed main() { fastIO(); solve(); }
#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...