Submission #344724

#	Time	Username	Problem	Language	Result	Execution time	Memory
344724		mansur	Divide and conquer (IZhO14_divide)	C++14	100 / 100	46 ms	12268 KiB

divide

#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(400001);
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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52