oj.uz

답안 #1072797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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";
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 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 -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2064 ms 1628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2052 ms 3156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 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 -