Submission #338866

# Submission time Handle Problem Language Result Execution time Memory
338866 2020-12-24T05:36:54 Z katearima Divide and conquer (IZhO14_divide) C++14
0 / 100
1 ms 364 KB
#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;
		int cost=d[b]-v[b].x;
		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 l=0; int r=mn.size()-1;
		while(l<=r){
			mid=(l+r)/2;
			if(mn[mid].val<=cost) r=mid-1;
			else l=mid+1;
		}
		a=mn[mid].ind;
		ans=max(ans, g[b]-g[a-1]);		
	}
	cout<<ans<<endl;
}

Compilation message

divide.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      |      ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -