Submission #338986

#	Time	Username	Problem	Language	Result	Execution time	Memory
338986		katearima	Divide and conquer (IZhO14_divide)	C++14	100 / 100	276 ms	19420 KiB

divide

#include <bits/stdc++.h>
#define ll long long
#define val first
#define ind second
using namespace std;
const int N=1e5+5;
int n,a,b,x;
ll ans;
typedef struct{
	int x, gold , energy;
}camp;
vector<camp> v;
vector<pair<ll, int>> mn;
map <int, ll> g, d;
main(){
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>x>>a>>b;
		v.push_back({x,a,b});
	}
	g[0]=v[0].gold; d[0]=v[0].energy;
	for(int i=1; i<n; i++){
		g[i]=g[i-1]+v[i].gold;
		d[i]=d[i-1]+v[i].energy;
	}
	a=0;
	for(int i=0; i<n; i++){
		b=i; int mid=0;
		
		if(mn.size()==0 || mn[mn.size()-1].val>d[b-1]-v[b].x){
			mn.push_back({d[b-1]-v[b].x,i}); 
		}
		int cost=d[b]-v[b].x;
		int l=0; int r=mn.size()-1;
		while(l<=r){
			mid=(l+r)/2;
			if(mn[mid].val<=cost) {
				r=mid-1;
				a=mn[mid].ind;
			}
			else l=mid+1;
		}
		//a=mn[mid].ind;
		ans=max(ans, g[b]-g[a-1]);
		//cout<<a<<" "<<b<<" "<<mid<<" "<<mn[mid].val<<" "<<g[b]-g[a-1]<<endl;	
	}
	cout<<ans<<endl;
}

/*
x2-x1 <= d[e2]-d[e1-1]
d[e2]-x2 >= kiki sworia swoooooooria aia    aa a  a 
*/

Compilation message (stderr)

divide.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      |      ^

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