Submission #413081

#	Time	Username	Problem	Language	Result	Execution time	Memory
413081		hhh07	Global Warming (CEOI18_glo)	C++14	0 / 100	65 ms	6936 KiB

glo

#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <climits>
#include <vector>
#include <queue>
#include <utility>
#include <iomanip>
#include <cstring>
#include <sstream>
#include <string>
#include <stack>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll n, x;
    cin >> n >> x;
    ll t[n];
    for (int i = 0; i < n; i++)
        cin >> t[i];

    vi dp(n, INT_MAX), pref(n);
    ll res = 0;
    for (int i = 0; i < n; i++){
        ll j = upper_bound(dp.begin(), dp.end(), t[i]) - dp.begin();

        dp[j] = t[i];
        pref[i] = j + 1;
        res = max(res, j + 1);
    }

    dp.assign(n, INT_MAX);

    for (int i = n - 1; i >= 0; i--){
        int j = upper_bound(dp.begin(), dp.end(), -t[i] + x) - dp.begin();

        res = max(res, pref[i] + j - 1);

        j = upper_bound(dp.begin(), dp.end(), -t[i]) - dp.begin();
        dp[j] = -t[i];

    }


    cout << res << endl;
}

• 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