Submission #873818

#TimeUsernameProblemLanguageResultExecution timeMemory
873818MisterReaperGlobal Warming (CEOI18_glo)C++17
100 / 100
50 ms3812 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; const int INF = 2E9; ostream& operator<< (ostream& out, vector <int> dp) { out << "{"; for(int i = 0; i < int(dp.size()); i++) { out << (abs(dp[i]) == INF ? -23 : dp[i]); if(i +1 != int(dp.size())) out << ", "; } return out << "}"; } #define ONLINE_JUDGE void solve() { int n, x; cin >> n >> x; vector <int> t(n +1); for(int i = 1; i <= n; i++) cin >> t[i]; vector <int> dp(n +1, INF), left(n +1); for(int i = 1; i <= n; i++) { int idx = lower_bound(dp.begin(), dp.end(), t[i]) - dp.begin(); dp[idx] = t[i]; left[i] = idx +1; } dp = vector <int> (n +1, -INF); int ans = 0; for(int i = n; i >= 1; i--) { int idx = lower_bound(dp.begin(), dp.end(), t[i] - x, greater <int> ()) - dp.begin(); //cerr << i << " || " << t[i] - x << " :: " << left[i] << " " << idx << " -> " << dp << "\n"; ans = max(ans, left[i] + idx); idx = lower_bound(dp.begin(), dp.end(), t[i], greater <int> ()) - dp.begin(); dp[idx] = t[i]; } cout << ans; return; } signed main() { #ifndef ONLINE_JUDGE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { 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...