Submission #1214943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214943		mariamp1	Global Warming (CEOI18_glo)	C++20	0 / 100	70 ms	2712 KiB

glo

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int INF = 1e9 + 7;
int main(){
    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, INF);
    vector<int> pref(n+1);
    for(int i = 1; i <= n; i++){
        int len = lower_bound(dp.begin() + 1, dp.end(), a[i] - x) - dp.begin();
        dp[len] = a[i] - x;
        pref[i] = len;
        ans = max(ans, len);
    }
    for(int i = 0; i <= n; i++){
        dp[i] = INF;
    }
    for(int i = 1; i <= n; i++){
        int len = lower_bound(dp.begin() + 1, dp.end(), -(a[i] - x)) - dp.begin();
        int idx = n - i +1;
        ans = max(ans, pref[idx] + len - 1);
        len = lower_bound(dp.begin() + 1, dp.end(), -a[i]) - dp.begin();
        dp[len] = -a[i];
    }
    cout << ans << endl;
    return 0;
}

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