oj.uz

답안 #1069237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1069237 2024-08-21T17:55:38 Z PotatoTheWarriorFRTT Global Warming (CEOI18_glo) C++14
25 / 100
 2000 ms 5468 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
ll p1 = 27644437;
ll p2 = 1000000007;
 
int LIS(int n, ll a[]) {
    ll dp[n+1]; // dp[l] = smallest element at which a sequence of size l ends;
    int ans = 1;
    dp[1] = a[0];
    for(int i=1;i<n;i++) {
        if(dp[ans] < a[i]) {
            ans++;
            dp[ans] = a[i];
        }else if(a[i] < dp[1]) {
            dp[1] = a[i];
        }else{
            int r = ans;
            int l = 1;
            while(r - l > 1) {
                int m = (r+l)/2;
                if(a[i] < dp[m]) {
                    r = m;
                }else if(a[i] >= dp[m]) {
                    l = m;
                }
            }
            if(dp[l] != a[i]) {
                dp[r] = a[i]; 
            }
            
        }
    }
    return ans;
}

void solve() {
    int n, x; cin >> n >> x;
    ll a[n+1];
 
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    if(x == 0) {
        cout << LIS(n, a) << endl;
    }else{
        int ans = 1;
        x=abs(x);
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                for(int d=-x;d<=x;d++) {
                    for(int k=i;k<=j;k++) {
                        a[k]+=d;
                    }
                    ans = max(ans, LIS(n, a));
                    for(int k=i;k<=j;k++) {
                        a[k]-=d;
                    }
                }
            }
        }
        cout << ans << endl;
    }
 
}
int main()   {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // int t; cin >> t;
    // while(t--) 
        solve();
 
    char dksfjn;
    cin >> dksfjn;
}

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 348 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 348 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 348 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 14 ms 452 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 63 ms 436 KB Output is correct
15 Correct 15 ms 344 KB Output is correct
16 Correct 14 ms 348 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 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 348 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 14 ms 452 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 63 ms 436 KB Output is correct
15 Correct 15 ms 344 KB Output is correct
16 Correct 14 ms 348 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 2089 ms 348 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 5468 KB Output is correct
2 Correct 19 ms 5468 KB Output is correct
3 Correct 21 ms 5460 KB Output is correct
4 Correct 25 ms 5440 KB Output is correct
5 Correct 15 ms 4696 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2060 ms 2908 KB Time limit exceeded
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 348 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 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 14 ms 452 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 63 ms 436 KB Output is correct
15 Correct 15 ms 344 KB Output is correct
16 Correct 14 ms 348 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 2089 ms 348 KB Time limit exceeded
20 Halted 0 ms 0 KB -