Submission #370594

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
370594	2021-02-24T07:52:56 Z	Seanliu	Bigger segments (IZhO19_segments)	C++17	37 / 100	192 ms	7788 KB

segments

#include <iostream>
#include <utility>
#include <algorithm>
#include <deque>
#define pii pair<int,int> 
#define F first
#define S second
#define int long long int
using namespace std;

const int maxN = 5e3 + 326;
int N, arr[maxN];

deque<pii> dandiao[maxN];

signed main(){
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> arr[i];
		arr[i] += arr[i - 1];
	}
	dandiao[0].push_back({0, 0});
	int ans = 0;
	for(int i = 1; i <= N; i++){
		deque<pii> tmp = deque<pii>();
		//cout << "i = " << i << endl;
		for(int j = 0; j < i; j++){
			auto p = upper_bound(dandiao[j].begin(), dandiao[j].end(), pii{arr[i] - arr[j], maxN});
			if(p == dandiao[j].begin()) continue;
			p--;
			//cout << "j = " << j << endl;
			//cout << "Found: " << p->F << " " << p->S << endl;
			tmp.emplace_back(arr[i] - arr[j], p->S + 1);
			//cout << "j = " << j << ", ans = " << p->S + 1 << endl;
			ans = max(ans, p->S + 1);
		}
		sort(tmp.begin(), tmp.end());
		for(auto [s, x] : tmp){
			if(!dandiao[i].size() || dandiao[i].back().S < x) dandiao[i].emplace_back(s, x);
		}
	}
	cout << ans << endl;
}

Subtask #1
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3948 KB	Output is correct
2	Correct	3 ms	3948 KB	Output is correct
3	Correct	3 ms	3948 KB	Output is correct
4	Correct	3 ms	3948 KB	Output is correct
5	Correct	3 ms	3948 KB	Output is correct
6	Correct	3 ms	3948 KB	Output is correct
7	Correct	3 ms	3948 KB	Output is correct
8	Correct	3 ms	3948 KB	Output is correct
9	Correct	3 ms	3948 KB	Output is correct
10	Correct	3 ms	3948 KB	Output is correct
11	Correct	3 ms	4076 KB	Output is correct
12	Correct	3 ms	3948 KB	Output is correct
13	Correct	3 ms	3948 KB	Output is correct
14	Correct	3 ms	3948 KB	Output is correct
15	Correct	3 ms	3948 KB	Output is correct

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3948 KB	Output is correct
2	Correct	3 ms	3948 KB	Output is correct
3	Correct	3 ms	3948 KB	Output is correct
4	Correct	3 ms	3948 KB	Output is correct
5	Correct	3 ms	3948 KB	Output is correct
6	Correct	3 ms	3948 KB	Output is correct
7	Correct	3 ms	3948 KB	Output is correct
8	Correct	3 ms	3948 KB	Output is correct
9	Correct	3 ms	3948 KB	Output is correct
10	Correct	3 ms	3948 KB	Output is correct
11	Correct	3 ms	4076 KB	Output is correct
12	Correct	3 ms	3948 KB	Output is correct
13	Correct	3 ms	3948 KB	Output is correct
14	Correct	3 ms	3948 KB	Output is correct
15	Correct	3 ms	3948 KB	Output is correct
16	Correct	4 ms	3948 KB	Output is correct
17	Correct	7 ms	3948 KB	Output is correct
18	Correct	8 ms	3948 KB	Output is correct
19	Correct	7 ms	3948 KB	Output is correct
20	Correct	8 ms	3948 KB	Output is correct
21	Correct	7 ms	3948 KB	Output is correct
22	Correct	6 ms	3948 KB	Output is correct
23	Correct	4 ms	3948 KB	Output is correct
24	Correct	7 ms	3948 KB	Output is correct
25	Correct	7 ms	3948 KB	Output is correct
26	Correct	7 ms	3948 KB	Output is correct
27	Correct	6 ms	3948 KB	Output is correct
28	Correct	7 ms	3948 KB	Output is correct
29	Correct	7 ms	3948 KB	Output is correct
30	Correct	7 ms	3948 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3948 KB	Output is correct
2	Correct	3 ms	3948 KB	Output is correct
3	Correct	3 ms	3948 KB	Output is correct
4	Correct	3 ms	3948 KB	Output is correct
5	Correct	3 ms	3948 KB	Output is correct
6	Correct	3 ms	3948 KB	Output is correct
7	Correct	3 ms	3948 KB	Output is correct
8	Correct	3 ms	3948 KB	Output is correct
9	Correct	3 ms	3948 KB	Output is correct
10	Correct	3 ms	3948 KB	Output is correct
11	Correct	3 ms	4076 KB	Output is correct
12	Correct	3 ms	3948 KB	Output is correct
13	Correct	3 ms	3948 KB	Output is correct
14	Correct	3 ms	3948 KB	Output is correct
15	Correct	3 ms	3948 KB	Output is correct
16	Correct	4 ms	3948 KB	Output is correct
17	Correct	7 ms	3948 KB	Output is correct
18	Correct	8 ms	3948 KB	Output is correct
19	Correct	7 ms	3948 KB	Output is correct
20	Correct	8 ms	3948 KB	Output is correct
21	Correct	7 ms	3948 KB	Output is correct
22	Correct	6 ms	3948 KB	Output is correct
23	Correct	4 ms	3948 KB	Output is correct
24	Correct	7 ms	3948 KB	Output is correct
25	Correct	7 ms	3948 KB	Output is correct
26	Correct	7 ms	3948 KB	Output is correct
27	Correct	6 ms	3948 KB	Output is correct
28	Correct	7 ms	3948 KB	Output is correct
29	Correct	7 ms	3948 KB	Output is correct
30	Correct	7 ms	3948 KB	Output is correct
31	Correct	45 ms	3948 KB	Output is correct
32	Correct	143 ms	3948 KB	Output is correct
33	Correct	174 ms	3948 KB	Output is correct
34	Correct	140 ms	3948 KB	Output is correct
35	Correct	181 ms	4204 KB	Output is correct
36	Correct	183 ms	4332 KB	Output is correct
37	Correct	141 ms	3948 KB	Output is correct
38	Correct	77 ms	3948 KB	Output is correct
39	Correct	172 ms	4136 KB	Output is correct
40	Correct	174 ms	4220 KB	Output is correct
41	Correct	176 ms	3948 KB	Output is correct
42	Correct	153 ms	4204 KB	Output is correct
43	Correct	145 ms	3948 KB	Output is correct
44	Correct	192 ms	3948 KB	Output is correct
45	Correct	176 ms	4076 KB	Output is correct

Subtask #4
0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3948 KB	Output is correct
2	Correct	3 ms	3948 KB	Output is correct
3	Correct	3 ms	3948 KB	Output is correct
4	Correct	3 ms	3948 KB	Output is correct
5	Correct	3 ms	3948 KB	Output is correct
6	Correct	3 ms	3948 KB	Output is correct
7	Correct	3 ms	3948 KB	Output is correct
8	Correct	3 ms	3948 KB	Output is correct
9	Correct	3 ms	3948 KB	Output is correct
10	Correct	3 ms	3948 KB	Output is correct
11	Correct	3 ms	4076 KB	Output is correct
12	Correct	3 ms	3948 KB	Output is correct
13	Correct	3 ms	3948 KB	Output is correct
14	Correct	3 ms	3948 KB	Output is correct
15	Correct	3 ms	3948 KB	Output is correct
16	Correct	4 ms	3948 KB	Output is correct
17	Correct	7 ms	3948 KB	Output is correct
18	Correct	8 ms	3948 KB	Output is correct
19	Correct	7 ms	3948 KB	Output is correct
20	Correct	8 ms	3948 KB	Output is correct
21	Correct	7 ms	3948 KB	Output is correct
22	Correct	6 ms	3948 KB	Output is correct
23	Correct	4 ms	3948 KB	Output is correct
24	Correct	7 ms	3948 KB	Output is correct
25	Correct	7 ms	3948 KB	Output is correct
26	Correct	7 ms	3948 KB	Output is correct
27	Correct	6 ms	3948 KB	Output is correct
28	Correct	7 ms	3948 KB	Output is correct
29	Correct	7 ms	3948 KB	Output is correct
30	Correct	7 ms	3948 KB	Output is correct
31	Correct	45 ms	3948 KB	Output is correct
32	Correct	143 ms	3948 KB	Output is correct
33	Correct	174 ms	3948 KB	Output is correct
34	Correct	140 ms	3948 KB	Output is correct
35	Correct	181 ms	4204 KB	Output is correct
36	Correct	183 ms	4332 KB	Output is correct
37	Correct	141 ms	3948 KB	Output is correct
38	Correct	77 ms	3948 KB	Output is correct
39	Correct	172 ms	4136 KB	Output is correct
40	Correct	174 ms	4220 KB	Output is correct
41	Correct	176 ms	3948 KB	Output is correct
42	Correct	153 ms	4204 KB	Output is correct
43	Correct	145 ms	3948 KB	Output is correct
44	Correct	192 ms	3948 KB	Output is correct
45	Correct	176 ms	4076 KB	Output is correct
46	Runtime error	9 ms	7788 KB	Execution killed with signal 11
47	Halted	0 ms	0 KB	-

Subtask #5
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	3948 KB	Output is correct
2	Correct	3 ms	3948 KB	Output is correct
3	Correct	3 ms	3948 KB	Output is correct
4	Correct	3 ms	3948 KB	Output is correct
5	Correct	3 ms	3948 KB	Output is correct
6	Correct	3 ms	3948 KB	Output is correct
7	Correct	3 ms	3948 KB	Output is correct
8	Correct	3 ms	3948 KB	Output is correct
9	Correct	3 ms	3948 KB	Output is correct
10	Correct	3 ms	3948 KB	Output is correct
11	Correct	3 ms	4076 KB	Output is correct
12	Correct	3 ms	3948 KB	Output is correct
13	Correct	3 ms	3948 KB	Output is correct
14	Correct	3 ms	3948 KB	Output is correct
15	Correct	3 ms	3948 KB	Output is correct
16	Correct	4 ms	3948 KB	Output is correct
17	Correct	7 ms	3948 KB	Output is correct
18	Correct	8 ms	3948 KB	Output is correct
19	Correct	7 ms	3948 KB	Output is correct
20	Correct	8 ms	3948 KB	Output is correct
21	Correct	7 ms	3948 KB	Output is correct
22	Correct	6 ms	3948 KB	Output is correct
23	Correct	4 ms	3948 KB	Output is correct
24	Correct	7 ms	3948 KB	Output is correct
25	Correct	7 ms	3948 KB	Output is correct
26	Correct	7 ms	3948 KB	Output is correct
27	Correct	6 ms	3948 KB	Output is correct
28	Correct	7 ms	3948 KB	Output is correct
29	Correct	7 ms	3948 KB	Output is correct
30	Correct	7 ms	3948 KB	Output is correct
31	Correct	45 ms	3948 KB	Output is correct
32	Correct	143 ms	3948 KB	Output is correct
33	Correct	174 ms	3948 KB	Output is correct
34	Correct	140 ms	3948 KB	Output is correct
35	Correct	181 ms	4204 KB	Output is correct
36	Correct	183 ms	4332 KB	Output is correct
37	Correct	141 ms	3948 KB	Output is correct
38	Correct	77 ms	3948 KB	Output is correct
39	Correct	172 ms	4136 KB	Output is correct
40	Correct	174 ms	4220 KB	Output is correct
41	Correct	176 ms	3948 KB	Output is correct
42	Correct	153 ms	4204 KB	Output is correct
43	Correct	145 ms	3948 KB	Output is correct
44	Correct	192 ms	3948 KB	Output is correct
45	Correct	176 ms	4076 KB	Output is correct
46	Runtime error	9 ms	7788 KB	Execution killed with signal 11
47	Halted	0 ms	0 KB	-

Submission #370594

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 14.0 / 14.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 36.0

Subtask #5 0 / 27.0

Subtask #1
13.0 / 13.0

Subtask #2
14.0 / 14.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 36.0

Subtask #5
0 / 27.0