oj.uz

Submission #413081

# Submission time Handle Problem Language Result Execution time Memory
413081 2021-05-28T08:11:13 Z hhh07 Global Warming (CEOI18_glo) C++14
0 / 100
 65 ms 6936 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6932 KB Output is correct
2 Correct 63 ms 6844 KB Output is correct
3 Correct 64 ms 6936 KB Output is correct
4 Correct 65 ms 6848 KB Output is correct
5 Incorrect 56 ms 6112 KB Output isn't correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1868 KB Output is correct
2 Correct 15 ms 1956 KB Output is correct
3 Correct 15 ms 1856 KB Output is correct
4 Incorrect 13 ms 1792 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 3632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -