Submission #332415

#	Time	Username	Problem	Language	Result	Execution time	Memory
332415		nandonathaniel	Divide and conquer (IZhO14_divide)	C++14	100 / 100	137 ms	18560 KiB

divide

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005,INF=1e9;

long long prefg[MAXN],prefd[MAXN];
int x[MAXN],bit[2*MAXN],MAX;
map<long long,int> mp;

int query(int now){
	int ret=INF;
	for(int i=now;i>0;i-=(i&(-i)))ret=min(ret,bit[i]);
	return ret;
}

void update(int now,int val){
	for(int i=now;i<=MAX;i+=(i&(-i)))bit[i]=min(bit[i],val);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i=0;i<2*MAXN;i++)bit[i]=INF;
	int n,g,d;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> x[i];
		cin >> g >> d;
		prefg[i]=prefg[i-1]+g;
		prefd[i]=prefd[i-1]+d;
	}
	for(int i=0;i<=n;i++){
		mp[prefd[i]-x[i+1]];
		if(i)mp[prefd[i]-x[i]];
	}
	for(map<long long,int>::iterator it=mp.begin();it!=mp.end();++it){
		MAX++;
		mp[it->first]=MAX;
	}
	long long ans=0;
	update(mp[prefd[0]-x[1]],1);
	for(int i=1;i<=n;i++){
		int idx=query(mp[prefd[i]-x[i]]);
		if(idx!=INF){
			ans=max(ans,prefg[i]-prefg[idx-1]);
		}
		update(mp[prefd[i]-x[i+1]],i+1);
	}
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52