Submission #1072797

# Submission time Handle Problem Language Result Execution time Memory
1072797 2024-08-24T05:03:18 Z HappyCapybara Global Warming (CEOI18_glo) C++17
25 / 100
2000 ms 5716 KB
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> st;

void update(int pos, int val, int node=1, int tl=0, int tr=n-1){
    if (tl == tr){
        st[node] = val;
        return;
    }
    int tm = (tl+tr)/2;
    if (pos <= tm) update(pos, val, node*2, tl, tm);
    else update(pos, val, node*2+1, tm+1, tr);
    st[node] = max(st[node*2], st[node*2+1]);
}

int query(int l, int r, int node=1, int tl=0, int tr=n-1){
    if (l <= tl && tr <= r) return st[node];
    int tm = (tl+tr)/2;
    int res = 0;
    if (l <= tm) res = max(res, query(l, r, node*2, tl, tm));
    if (tm+1 <= r) res = max(res, query(l, r, node*2+1, tm+1, tr));
    return res;
}

int main(){
    int x;
    cin >> n >> x;
    vector<int> v(n);
    for (int i=0; i<n; i++) cin >> v[i];
    st.resize(4*n, 0);

    vector<pair<int,int>> p(n);
    for (int i=0; i<n; i++) p[i] = {v[i], -i};

    sort(p.begin(), p.end());

    for (int i=n-1; i>=0; i--){
        int j = -p[i].second;
        int bsf = query(j, n-1);
        update(j, bsf+1);
    }

    int res = st[1];

    if (x == 0){
        cout << res << "\n";
        return 0;
    }

    for (int i=0; i<n; i++){
        for (int j=i; j<n; j++){
            for (int k=-x; k<=x; k++){
                if (k == 0) continue;
                for (int l=0; l<n; l++){
                    if (i <= l && l <= j) p[l] = {v[l]+k, -l};
                    else p[l] = {v[l], -l};
                }
                sort(p.begin(), p.end());
                for (int l=0; l<4*n; l++) st[l] = 0;
                for (int l=n-1; l>=0; l--){
                    int m = -p[l].second;
                    int bsf = query(m, n-1);
                    update(m, bsf+1);
                }
                res = max(res, st[1]);
            }
        }
    }

    cout << res << "\n";
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 121 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 377 ms 348 KB Output is correct
15 Correct 150 ms 348 KB Output is correct
16 Correct 143 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 121 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 377 ms 348 KB Output is correct
15 Correct 150 ms 348 KB Output is correct
16 Correct 143 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Execution timed out 2099 ms 344 KB Time limit exceeded
20 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 117 ms 5716 KB Output is correct
2 Correct 125 ms 5712 KB Output is correct
3 Correct 119 ms 5716 KB Output is correct
4 Correct 119 ms 5712 KB Output is correct
5 Correct 82 ms 5712 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 1628 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 3156 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 432 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 121 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 377 ms 348 KB Output is correct
15 Correct 150 ms 348 KB Output is correct
16 Correct 143 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Execution timed out 2099 ms 344 KB Time limit exceeded
20 Halted 0 ms 0 KB -