Submission #1251232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251232		rcll	Global Warming (CEOI18_glo)	C++20	100 / 100	72 ms	3428 KiB

glo

#include <bits/stdc++.h>
using namespace std; 
int temps[200005];
int pref_longest[200005];

int main() {
    int n;
    int x;
    cin >> n >> x;
    for (int i=0; i<n; i++) {
        cin >> temps[i];
    }
    vector<int> dp(n,INT_MAX);
    int longest=0;
    for (int i=0; i<n; i++) {
        int j=lower_bound(dp.begin(),dp.end(),temps[i])-dp.begin();
        dp[j]=temps[i];
        pref_longest[i]=j+1;
        longest=max(longest,pref_longest[i]);
    }
    dp=vector<int>(n,INT_MAX);
    for (int i=n-1; i>=0; i--) {
        int pos=lower_bound(dp.begin(),dp.end(),-temps[i]+x)-dp.begin();
        longest=max(longest, pref_longest[i]+pos);
        int insert_pos=lower_bound(dp.begin(),dp.end(),-temps[i])-dp.begin();
        dp[insert_pos]=-temps[i];
    }
    cout << longest << '\n';
}

• 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