oj.uz

Submission #959044

# Submission time Handle Problem Language Result Execution time Memory
959044 2024-04-07T12:17:26 Z Nelt Global Warming (CEOI18_glo) C++17
28 / 100
 2000 ms 10056 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 460 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 4 ms 348 KB Output is correct
20 Correct 4 ms 468 KB Output is correct
21 Correct 3 ms 344 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 3 ms 344 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 10056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 2648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 5212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 1 ms 452 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 376 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 4 ms 348 KB Output is correct
20 Correct 4 ms 468 KB Output is correct
21 Correct 3 ms 344 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 2 ms 600 KB Output is correct
26 Correct 3 ms 344 KB Output is correct
27 Execution timed out 2054 ms 10056 KB Time limit exceeded
28 Halted 0 ms 0 KB -