Submission #1111161

#TimeUsernameProblemLanguageResultExecution timeMemory
1111161Ghulam_JunaidGlobal Warming (CEOI18_glo)C++17
100 / 100
87 ms5448 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 2e9 + 10; int main(){ int n, x; cin >> n >> x; int a[n]; for (int i=0; i<n; i++) cin >> a[i]; int ans = 0; int pref[n] = {0}; int suf[n] = {0}; int dp[n + 1]; for (int i = 1; i <= n; i ++) dp[i] = inf; dp[0] = -inf; for (int i = n - 1; i >= 0; i --){ int lb = lower_bound(dp, dp + n + 1, -a[i]) - dp; suf[i] = lb; int ub = lower_bound(dp, dp + n + 1, -(a[i] + x)) - dp; dp[ub] = -(a[i] + x); } for (int i = 1; i <= n; i ++) dp[i] = inf; dp[0] = -inf; for (int i = 0; i < n; i ++){ int ub = lower_bound(dp, dp + n + 1, a[i]) - dp; dp[ub] = a[i]; ans = max(ans, ub + suf[i] - 1); } cout << ans << endl; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:15:9: warning: unused variable 'pref' [-Wunused-variable]
   15 |     int pref[n] = {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...