답안 #173038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
173038	2020-01-03T07:37:00 Z	LinusTorvaldsFan	Bigger segments (IZhO19_segments)	C++14	37 / 100	1500 ms	2680 KB

segments

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Node{
	pair<int,int>val;
	Node*left;
	Node*right;
	Node() {
		val={0,0};
		left=nullptr;
		right=nullptr;
	}
};

pair<int,int>get_val(Node *root){
	if(root==nullptr)return make_pair(0,0);
	return root->val;
}


void update(Node *root, ll p, int x, int y, ll l, ll r) {
	if(l==p && r==p){
		root->val=max(make_pair(x,y),root->val);
		return;
	}
	ll m=(l+r)/2;
	if(l<=p&&p<=m){
		if(root->left==nullptr){
			root->left=new Node;
		}
		update(root->left,p,x,y,l,m);
	}
	if(m+1<=p&&p<=r){
		if(root->right==nullptr){
			root->right=new Node;
		}
		update(root->right,p,x,y,m+1,r);
	}
	root->val=max(get_val(root->left),get_val(root->right));
}

pair<int,int> get(Node *root, ll l, ll r, ll lx, ll rx){
	if(l>rx || lx>r) {
		return {0,0};
	}
	if(l<=lx && rx<=r){
		return root->val;
	}
	ll mx=(lx+rx)/2;
	pair<int,int> ans={0,0};
	if(root->right!=nullptr){
		ans=max(ans,get(root->right,l,r, mx+1, rx));
	}
	if(root->left!=nullptr){
		ans=max(ans,get(root->left,l,r, lx, mx));
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	
	vector<ll>pr(n+1);
	for(int i=0;i<n;i++)pr[i+1]=pr[i]+a[i];
	vector<int>ans(n);
	vector<ll> ans_sum(n);
	ll sum=0;
	for(int i=0;i<n;i++){
		sum+=a[i];
		ans_sum[i]=sum;
		ans[i]=1;
	}
	Node *tree=new Node;
	update(tree,ans_sum[0]+pr[1],ans[0],0, 0, 1e15);
	for(int i=1;i<n;i++){
		for(int j=i-1;j>=0;j--){
			if(pr[i+1]>=ans_sum[j]+pr[j+1]){
				ans[i]=ans[j]+1;
				ans_sum[i]=pr[i+1]-pr[j+1];
				break;
			}
		}
		
	}
	cout<<ans[n-1];
	return 0;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	276 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	276 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	328 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	380 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	296 KB	Output is correct
29	Correct	3 ms	376 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	276 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	328 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	380 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	296 KB	Output is correct
29	Correct	3 ms	376 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	6 ms	376 KB	Output is correct
32	Correct	3 ms	380 KB	Output is correct
33	Correct	3 ms	452 KB	Output is correct
34	Correct	3 ms	376 KB	Output is correct
35	Correct	3 ms	376 KB	Output is correct
36	Correct	3 ms	376 KB	Output is correct
37	Correct	2 ms	376 KB	Output is correct
38	Correct	2 ms	376 KB	Output is correct
39	Correct	2 ms	376 KB	Output is correct
40	Correct	3 ms	376 KB	Output is correct
41	Correct	2 ms	376 KB	Output is correct
42	Correct	3 ms	380 KB	Output is correct
43	Correct	3 ms	376 KB	Output is correct
44	Correct	2 ms	376 KB	Output is correct
45	Correct	2 ms	376 KB	Output is correct

Subtask #4
0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	276 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	328 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	380 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	296 KB	Output is correct
29	Correct	3 ms	376 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	6 ms	376 KB	Output is correct
32	Correct	3 ms	380 KB	Output is correct
33	Correct	3 ms	452 KB	Output is correct
34	Correct	3 ms	376 KB	Output is correct
35	Correct	3 ms	376 KB	Output is correct
36	Correct	3 ms	376 KB	Output is correct
37	Correct	2 ms	376 KB	Output is correct
38	Correct	2 ms	376 KB	Output is correct
39	Correct	2 ms	376 KB	Output is correct
40	Correct	3 ms	376 KB	Output is correct
41	Correct	2 ms	376 KB	Output is correct
42	Correct	3 ms	380 KB	Output is correct
43	Correct	3 ms	376 KB	Output is correct
44	Correct	2 ms	376 KB	Output is correct
45	Correct	2 ms	376 KB	Output is correct
46	Execution timed out	1561 ms	2680 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

Subtask #5
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	276 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	328 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	380 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	296 KB	Output is correct
29	Correct	3 ms	376 KB	Output is correct
30	Correct	2 ms	376 KB	Output is correct
31	Correct	6 ms	376 KB	Output is correct
32	Correct	3 ms	380 KB	Output is correct
33	Correct	3 ms	452 KB	Output is correct
34	Correct	3 ms	376 KB	Output is correct
35	Correct	3 ms	376 KB	Output is correct
36	Correct	3 ms	376 KB	Output is correct
37	Correct	2 ms	376 KB	Output is correct
38	Correct	2 ms	376 KB	Output is correct
39	Correct	2 ms	376 KB	Output is correct
40	Correct	3 ms	376 KB	Output is correct
41	Correct	2 ms	376 KB	Output is correct
42	Correct	3 ms	380 KB	Output is correct
43	Correct	3 ms	376 KB	Output is correct
44	Correct	2 ms	376 KB	Output is correct
45	Correct	2 ms	376 KB	Output is correct
46	Execution timed out	1561 ms	2680 KB	Time limit exceeded
47	Halted	0 ms	0 KB	-

답안 #173038

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