Submission #959044

#	Time	Username	Problem	Language	Result	Execution time	Memory
959044		Nelt	Global Warming (CEOI18_glo)	C++17	28 / 100	2054 ms	10056 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

void solve()
{
    ll n, x;
    cin >> n >> x;
    ll a[n];
    for (ll &i : a)
        cin >> i;
    ll dp[n], dp2[n];
    pair<ll, ll> dp1[n];
    for (ll i = 0; i < n; i++)
    {
        dp[i] = 1;
        dp1[i] = make_pair(1, -x);
        dp2[i] = -1e18;
        for (ll j = 0; j < i; j++)
        {
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
            if (a[j] < a[i])
                dp1[i] = max(dp1[i], make_pair(dp1[j].first + 1, dp1[j].second));
            if (a[j] + dp1[j].second < a[i])
                dp2[i] = max(dp2[i], dp1[j].first + 1);
            if (a[j] < a[i])    dp2[i] = max(dp2[i], dp2[j] + 1);
            if (min(x, max(-x, a[j] - a[i] + 1)) + a[i] > a[j])
                dp1[i] = max(dp1[i], make_pair(dp[j] + 1, min(x, max(-x, a[j] - a[i] + 1))));
        }
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++)
        ans = max({ans, dp[i], dp2[i], dp1[i].first});
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        solve();
    cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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