oj.uz

Submission #344723

# Submission time Handle Problem Language Result Execution time Memory
344723 2021-01-06T10:48:06 Z mansur Divide and conquer (IZhO14_divide) C++14
48 / 100
 24 ms 7916 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define all(a) a.begin(),a.end()
#define ll long long
#define pb push_back
#define nl '\n'
#define popb pop_back()
#define sz size()
#define ld long double
#define ull unsigned long long
#define F first
#define S second
#define fix fixed<<setprecision
#define pii pair<int,int>
#define E exit (0)
#define int long long
const int inf=1e9;
int x[100001],g[100001],d[100001],p[100001],pp[100001];
vector<pii>t(100001);
void build(int u,int tl,int tr) {
	if (tl==tr) {
	 	t[u]={p[tl]-x[tl],tl};
	 	return;
	}	
	int mid=(tl+tr)/2;
	build(u*2,tl,mid);
	build(u*2+1,mid+1,tr);
	if (t[u*2].F>t[u*2+1].F) {
		t[u]=t[u*2];
	}else {
		t[u]=t[u*2+1];	
	}
}
int get(int u,int tl,int tr,int l,int r,int x) {
	if (tl==tr) {
		return tl;
	}
	int mid=(tl+tr)/2;
	if (t[u*2+1].F>=x) {
		return get(u*2+1,mid+1,tr,l,r,x);
	}
	return get(u*2,tl,mid,l,r,x);
}
signed main() {
	//freopen("planting.in","r",stdin);
	//freopen("planting.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>x[i]>>g[i]>>d[i];
		p[i]=p[i-1]+d[i];
		pp[i]=pp[i-1]+g[i];
	}
	build(1,1,n);
	int mx=0;
	for (int i=1;i<=n;i++) {
		int z=p[i-1]-x[i];
		mx=max(mx,pp[get(1,1,n,i,n,z)]-pp[i-1]);	
	}
	cout<<mx;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Output is correct
2 Correct 1 ms 1900 KB Output is correct
3 Correct 1 ms 1900 KB Output is correct
4 Correct 1 ms 1900 KB Output is correct
5 Correct 1 ms 1900 KB Output is correct
6 Correct 2 ms 1912 KB Output is correct
7 Correct 1 ms 1900 KB Output is correct
8 Correct 1 ms 1900 KB Output is correct
9 Correct 2 ms 1900 KB Output is correct
10 Correct 2 ms 1900 KB Output is correct
11 Correct 2 ms 1900 KB Output is correct
12 Correct 2 ms 1900 KB Output is correct
13 Correct 1 ms 1900 KB Output is correct
14 Correct 1 ms 1900 KB Output is correct
15 Correct 2 ms 1900 KB Output is correct
16 Correct 2 ms 1900 KB Output is correct
17 Correct 2 ms 1900 KB Output is correct
18 Correct 2 ms 2028 KB Output is correct
19 Correct 2 ms 2028 KB Output is correct
20 Correct 2 ms 1920 KB Output is correct
21 Correct 2 ms 2028 KB Output is correct
22 Correct 2 ms 2028 KB Output is correct
23 Correct 3 ms 2284 KB Output is correct
24 Correct 4 ms 2284 KB Output is correct

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1900 KB Output is correct
2 Correct 1 ms 1900 KB Output is correct
3 Correct 1 ms 1900 KB Output is correct
4 Correct 1 ms 1900 KB Output is correct
5 Correct 1 ms 1900 KB Output is correct
6 Correct 2 ms 1912 KB Output is correct
7 Correct 1 ms 1900 KB Output is correct
8 Correct 1 ms 1900 KB Output is correct
9 Correct 2 ms 1900 KB Output is correct
10 Correct 2 ms 1900 KB Output is correct
11 Correct 2 ms 1900 KB Output is correct
12 Correct 2 ms 1900 KB Output is correct
13 Correct 1 ms 1900 KB Output is correct
14 Correct 1 ms 1900 KB Output is correct
15 Correct 2 ms 1900 KB Output is correct
16 Correct 2 ms 1900 KB Output is correct
17 Correct 2 ms 1900 KB Output is correct
18 Correct 2 ms 2028 KB Output is correct
19 Correct 2 ms 2028 KB Output is correct
20 Correct 2 ms 1920 KB Output is correct
21 Correct 2 ms 2028 KB Output is correct
22 Correct 2 ms 2028 KB Output is correct
23 Correct 3 ms 2284 KB Output is correct
24 Correct 4 ms 2284 KB Output is correct
25 Correct 3 ms 2156 KB Output is correct
26 Correct 4 ms 2412 KB Output is correct
27 Correct 5 ms 2540 KB Output is correct
28 Runtime error 24 ms 7916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -