Submission #68547

#	Time	Username	Problem	Language	Result	Execution time	Memory
68547		ege_eksi	Divide and conquer (IZhO14_divide)	C++14	0 / 100	5 ms	560 KiB

divide

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<algorithm>

using namespace std;

struct range
{
	int start , end;
	long long int gold , energy;
};

int n;

int x[100000];
int g[100000];
int e[100000];

range first(range p1 , int start , int end)
{
	int t_start = p1.start;
	int t_end = p1.end;
	long long int total_g = p1.gold;
	long long int total_e = p1.energy;
	
	long long int max_g = p1.gold;
	long long int max_e = p1.gold;
	int m_start = p1.start;
	int m_end = p1.end;
	
	for(int i = t_end ; i <= end ; i++)
	{
		total_g += g[i];
		total_e += e[i];
		
		if(total_e >= x[i]-x[m_start])
		{
			m_end = i;
			max_g = total_g;
			max_e = total_e;
		}
	}
	
	total_g = max_g;
	total_e = max_e;
	
	for(int i = t_start ; i >= start ; i--)
	{
		total_g += g[i];
		total_e += e[i];
		
		if(total_e >= x[m_end]-x[i])
		{
			m_start = i;
			max_g = total_g;
			max_e = total_e;
		}
	}
	
	
	
	range x;
	x.start = m_start;
	x.end = m_end;
	x.gold = max_g;
	x.energy = max_e;
	
	return x;
}

range second(range p1 , int start , int end)
{
	int t_start = p1.start;
	int t_end = p1.end;
	long long int total_g = p1.gold;
	long long int total_e = p1.energy;
	
	long long int max_g = p1.gold;
	long long int max_e = p1.gold;
	int m_start = p1.start;
	int m_end = p1.end;
	
	for(int i = t_start ; i >= start ; i--)
	{
		total_g += g[i];
		total_e += e[i];
		
		if(total_e >= x[m_end]-x[i])
		{
			m_start = i;
			max_g = total_g;
			max_e = total_e;
		}
	}
	
	total_g = max_g;
	total_e = max_e;
	
	for(int i = t_end ; i <= end ; i++)
	{
		total_g += g[i];
		total_e += e[i];
		
		if(total_e >= x[i]-x[m_start])
		{
			m_end = i;
			max_g = total_g;
			max_e = total_e;
		}
	}
	
	
	range x;
	x.start = m_start;
	x.end = m_end;
	x.gold = max_g;
	x.energy = max_e;
	
	return x;
}

range f(int start , int end)
{
	if(start == end)
	{	
		range x;
		x.start = x.end = start;
		x.gold = g[start];
		x.energy = e[start];
		
		return x;
	}
	
	int mid = (start+end)/2;
	
	range p1 = f(start , mid);
	range p2 = f(mid+1 , end);
	
	range x1 = first(p1 , start , end);
	
	range x2 = second(p2 , start , end);
	
	if(x1.gold > x2.gold)
	{
		return x1;
	}
	
	return x2;
}


int main()
{
	scanf("%d",&n);
	
	for(int i = 0 ; i < n ; i++)
	{
		scanf("%d %d %d" ,&x[i] , &g[i] , &e[i]);
	}
	
	range p = f(0 , n-1);
	
	printf("%lli",p.gold);
	
	return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
divide.cpp:161:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d" ,&x[i] , &g[i] , &e[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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