Submission #1188584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188584		ffeyyaae_	Global Warming (CEOI18_glo)	C++20	100 / 100	36 ms	2504 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5, INF = 1e9;
int n, x, ans;
int dp[N], keep[N];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> x;
    for( int i=0;i<n;i++ ) cin >> keep[i];
    vector<int> tp;
    for( int i=0;i<n;i++ )
    {
        int idx = lower_bound( tp.begin(), tp.end(), keep[i] )-tp.begin();
        if( idx == tp.size() ) tp.push_back( keep[i] );
        else tp[idx] = keep[i];
        dp[i] = idx+1;
        ans = max( ans, dp[i] );
    }
    tp.clear();
    for( int i=n-1;i>=0;i-- )
    {
        int idx = lower_bound( tp.begin(), tp.end(), -keep[i]+x )-tp.begin();
        int temp = lower_bound( tp.begin(), tp.end(), -keep[i] )-tp.begin();
        if( temp == tp.size() ) tp.push_back( -keep[i] );
        else tp[temp] = -keep[i];
        ans = max( ans, dp[i]+idx );
    }
    cout << ans;
    return 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