Submission #920127

#	Time	Username	Problem	Language	Result	Execution time	Memory
920127		Ghulam_Junaid	Global Warming (CEOI18_glo)	C++17	27 / 100	96 ms	3664 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 ub = lower_bound(dp, dp + n + 1, -(a[i] + x)) - dp;
        dp[ub] = -(a[i] + x);
        int lb = lower_bound(dp, dp + n + 1, -a[i]) - dp;
        suf[i] = lb;
    }

    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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25