Submission #1111161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111161		Ghulam_Junaid	Global Warming (CEOI18_glo)	C++17	100 / 100	87 ms	5448 KiB

glo

#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};
      |         ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25