oj.uz

답안 #1094964

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1094964 2024-10-01T03:59:29 Z SoMotThanhXuan Global Warming (CEOI18_glo) C++17
25 / 100
 131 ms 5980 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 5;
int N, X, T[maxN];
namespace subtask1{
    bool check(){
        return X <= 50 && N <= 50;
    }
    int b[55], f[55];
    int res = 0;
    void sol(int a[]){
        for(int i = 1; i <= N; ++i)f[i] = 0;
        int ans = 0;
        for(int i = 1; i <= N; ++i){
            f[i] = 1;
            for(int j = 1; j < i; ++j){
                if(b[j] < b[i]) f[i] = max(f[i], f[j] + 1);
            }
            ans = max(ans, f[i]);
        }
        res = max(res, ans);
    }
    void solve(){
        for(int d = -X; d <= X; ++d){
            for(int i = 1; i <= N; ++i){
                for(int j = i; j <= N; ++j){
                    for(int k = 1; k <= N; ++k)b[k] = T[k];
                    for(int x = i; x <= j; ++x)b[x] += d;
                    sol(b);
                }
            }
        }
        cout << res;
    }
}
namespace subtask2{
    bool check(){
        return N <= 1000;
    }
    void solve(){

    }
}
namespace subtask3{
    int it[4 * maxN];
    int comp[maxN];
    bool check(){
        return X == 0;
    }
    void update(int id, int l, int r, int p, int v){
        if(l > p || r < p) return ;
        if(l == r){
            it[id] = v;
            return ;
        }
        int mid = l + r >> 1;
        if(p <= mid) update(id << 1, l, mid, p, v);
        else update(id << 1 | 1, mid + 1, r, p, v);
        it[id] = max(it[id << 1], it[id << 1 | 1]);
    }
    int get(int id, int l, int r, int u, int v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return it[id];
        int mid = l + r >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
    void solve(){
        for(int i = 1; i <= N; ++i)comp[i] = T[i];
        sort(comp + 1, comp + 1 + N);
        for(int i = 1; i <= N; ++i){
            T[i] = lower_bound(comp + 1, comp + 1 + N, T[i]) - comp;
            update(1, 1, N, T[i], get(1, 1, N, 1, T[i] - 1) + 1);
        }
        cout << it[1];
    }
}
namespace subtask4{
    bool check(){
        return X <= 5 && N <= 50000;
    }
    void solve(){

    }
}
namespace subtask5{
    bool check(){
        return X == 1000000000;
    }
    void solve(){

    }
}
namespace subtask6{
    void solve(){

    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> X;
    for(int i = 1; i <= N; ++i)cin >> T[i];
    if(subtask1 :: check()) return subtask1 :: solve(), 0;
    if(subtask2 :: check()) return subtask2 :: solve(), 0;
    if(subtask3 :: check()) return subtask3 :: solve(), 0;
    if(subtask4 :: check()) return subtask4 :: solve(), 0;
    if(subtask5 :: check()) return subtask5 :: solve(), 0;
    return subtask1 :: solve(), 0;
    return 0;
}
/*
8 0
7 3 5 12 2 7 3 4
*/

Compilation message

glo.cpp: In function 'void subtask3::update(int, int, int, int, int)':
glo.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~
glo.cpp: In function 'int subtask3::get(int, int, int, int, int)':
glo.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 44 ms 348 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 131 ms 348 KB Output is correct
15 Correct 58 ms 348 KB Output is correct
16 Correct 53 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 44 ms 348 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 131 ms 348 KB Output is correct
15 Correct 58 ms 348 KB Output is correct
16 Correct 53 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 5972 KB Output is correct
2 Correct 113 ms 5968 KB Output is correct
3 Correct 105 ms 5980 KB Output is correct
4 Correct 106 ms 5740 KB Output is correct
5 Correct 49 ms 4180 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 1628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 44 ms 348 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 131 ms 348 KB Output is correct
15 Correct 58 ms 348 KB Output is correct
16 Correct 53 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -