Submission #1068862

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1068862	2024-08-21T12:38:49 Z	PotatoTheWarriorFRTT	Global Warming (CEOI18_glo)	C++14	25 / 100	2000 ms	3556 KB

glo

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
ll p1 = 27644437;
ll p2 = 1000000007;

int LIS(int n, ll a[]) {
    const ll INF = 1e18;
    vector<ll> d(n+1, INF);
    d[0] = -INF;

    for (int i = 0; i < n; i++) {
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] < a[i] && a[i] < d[l])
            d[l] = a[i];
    }

    int ans = 0;
    for (int l = 0; l <= n; l++) {
        if (d[l] < INF)
            ans = l;
    }
    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

#	Verdict	Execution time	Memory	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	1 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	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	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	1 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	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 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	0 ms	348 KB	Output is correct
14	Correct	53 ms	348 KB	Output is correct
15	Correct	18 ms	444 KB	Output is correct
16	Correct	18 ms	344 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

#	Verdict	Execution time	Memory	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	1 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	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 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	0 ms	348 KB	Output is correct
14	Correct	53 ms	348 KB	Output is correct
15	Correct	18 ms	444 KB	Output is correct
16	Correct	18 ms	344 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Execution timed out	2051 ms	348 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	3420 KB	Output is correct
2	Correct	24 ms	3556 KB	Output is correct
3	Correct	24 ms	3420 KB	Output is correct
4	Correct	25 ms	3548 KB	Output is correct
5	Correct	16 ms	3556 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2063 ms	1236 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2037 ms	2016 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	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	1 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	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 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	0 ms	348 KB	Output is correct
14	Correct	53 ms	348 KB	Output is correct
15	Correct	18 ms	444 KB	Output is correct
16	Correct	18 ms	344 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Execution timed out	2051 ms	348 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-