Submission #397641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
397641	2021-05-02T16:34:18 Z	Victor	Global Warming (CEOI18_glo)	C++17	25 / 100	2000 ms	3292 KB

glo

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n, x, ans = 0, temps[200001];
    cin >> n >> x;
    vi subseq;

    rep(i, 0, n) cin >> temps[i];

    rep(l, -x, x + 1) {
        if (l)
            rep(j, 0, n) rep(k, j, n) {
                subseq.assign(n, 0);
                int longest = 0;
                rep(i, 0, n) {
                    int temp = temps[i];
                    if (j <= i && i <= k) temp += l;

                    int idx = lower_bound(subseq.begin(), subseq.begin() + longest, temp) - subseq.begin();
                    subseq[idx] = temp;
                    if (idx == longest) ++longest;
                }
                ans = max(ans, longest);
            }
        else {
            subseq.assign(n, 0);
            int longest = 0;
            rep(i, 0, n) {
                int temp = temps[i];

                int idx = lower_bound(subseq.begin(), subseq.begin() + longest, temp) - subseq.begin();
                subseq[idx] = temp;
                if (idx == longest) ++longest;
            }
            ans = max(ans, longest);
        }
    }

    cout << ans << endl;
    return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	17 ms	324 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	58 ms	204 KB	Output is correct
15	Correct	24 ms	204 KB	Output is correct
16	Correct	24 ms	316 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	17 ms	324 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	58 ms	204 KB	Output is correct
15	Correct	24 ms	204 KB	Output is correct
16	Correct	24 ms	316 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Execution timed out	2079 ms	332 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	3292 KB	Output is correct
2	Correct	38 ms	3200 KB	Output is correct
3	Correct	39 ms	3224 KB	Output is correct
4	Correct	38 ms	3276 KB	Output is correct
5	Correct	27 ms	3020 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2081 ms	1096 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	2079 ms	1996 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	17 ms	324 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	58 ms	204 KB	Output is correct
15	Correct	24 ms	204 KB	Output is correct
16	Correct	24 ms	316 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Execution timed out	2079 ms	332 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-