Submission #469445

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469445	2021-09-01T02:15:09 Z	dooompy	Global Warming (CEOI18_glo)	C++17	48 / 100	33 ms	4676 KB

glo

#include "bits/stdc++.h"

using namespace std;

using ll = long long;

int dp[100005];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, x; cin >> n >> x;
    vector<int> v(n);
    for (auto &a : v) cin >> a;

    int ans = 0;

    vector<int> lis;
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(lis.begin(), lis.end(), v[i]) - lis.begin();
        if (pos == lis.size()) {
            lis.push_back(v[i]);
        } else {
            lis[pos] = v[i];
        }
        dp[i] = pos + 1;
        ans = max(ans, dp[i]);
    }

    lis.clear();
    for (int i = n-1; i >= 0; i--) {
        int anspos = lower_bound(lis.begin(), lis.end(), -v[i] + x) - lis.begin();
        ans = max(ans, dp[i] + anspos);
        int pos = lower_bound(lis.begin(), lis.end(), -v[i]) - lis.begin();
        if (pos == lis.size()) {
            lis.push_back(-v[i]);
        } else {
            lis[pos] = -v[i];
        }
    }


    cout << ans;

}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if (pos == lis.size()) {
      |             ~~~~^~~~~~~~~~~~~
glo.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if (pos == lis.size()) {
      |             ~~~~^~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

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

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	216 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	216 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	32 ms	2772 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	716 KB	Output is correct
2	Correct	13 ms	672 KB	Output is correct
3	Correct	13 ms	660 KB	Output is correct
4	Correct	8 ms	912 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	8 ms	1228 KB	Output is correct
7	Correct	12 ms	1100 KB	Output is correct

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	1104 KB	Output is correct
2	Correct	26 ms	1100 KB	Output is correct
3	Runtime error	33 ms	4676 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	0 ms	216 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	0 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	1 ms	332 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Runtime error	32 ms	2772 KB	Execution killed with signal 11
28	Halted	0 ms	0 KB	-