oj.uz

Submission #68547

# Submission time Handle Problem Language Result Execution time Memory
68547 2018-08-17T09:35:07 Z ege_eksi Divide and conquer (IZhO14_divide) C++14
0 / 100
 5 ms 560 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 2 ms 356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 560 KB Output isn't correct
2 Halted 0 ms 0 KB -