Submission #1214664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214664		Bula	Global Warming (CEOI18_glo)	C++20	100 / 100	42 ms	2760 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, N = 2e5 + 5;
main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int tt = 1; //cin >> tt;
    while(tt--){
        int n, x;
        cin >> n >> x;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++) cin >> a[i];
        int ans = 0;
        vector<int> dp(n + 1, 1e9), p(n + 1);
        for(int i = 1; i <= n; i++){
            int j = lower_bound(dp.begin() + 1, dp.end(), a[i] - x) - dp.begin();
            dp[j] = a[i] - x; p[i] = j;
            ans = max(ans, j);
        }
        for(int i = 1; i <= n; i++) dp[i] = 1e9;
        reverse(a.begin() + 1, a.end());
        for(int i = 1; i <= n; i++){
            int j = lower_bound(dp.begin() + 1, dp.end(), -(a[i] - x)) - dp.begin();
            ans = max(ans, p[n - i + 1] + j - 1);
            j = lower_bound(dp.begin() + 1, dp.end(), -a[i]) - dp.begin();
            dp[j] = -a[i];
        }
        cout << ans << '\n';
    }
}

Compilation message (stderr)

glo.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    4 | main(){
      | ^~~~

• 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