Cod sursa(job #993060)

Utilizator ScoobyDoo38Nita Adrian Valentin ScoobyDoo38 Data 3 septembrie 2013 10:24:57
Problema Stalpi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>

using namespace std;

int main()
{
	ifstream in("stalpi.in");
	ofstream out("stalpi.out");

	int n;

	in >> n;

	vector< array< int, 6 > > x( n, array< int, 6 >() );

	for ( int i = 0 ; i < n; i++ )
		in >> x[ i ][ 0 ] >> x[ i ][ 1 ] >> x[ i ][ 2 ] >> x[ i ][ 3 ];

	sort( x.begin(), x.end() );

	for ( int i = 0; i < n; i++ )
	{
		for ( int j = 0; i - j >= 0 && x[ i ][ 0 ] - x[ i ][ 2 ] <= x[ i - j ][ 0 ]; j++ )
		{
			x[ i - j ][ 4 ]++;
			x[ i ][ 5 ]++;
		}

		for ( int j = 1; i + j < n && x[ i ][ 0 ] + x[ i ][ 3 ] >= x[ i + j ][ 0 ]; j++ )
		{
			x[ i + j ][ 4 ]++;
			x[ i ][ 5 ]++;
		}
	}

	vector< pair< float, int > > g( n );

	for ( int i = 0; i < n; i++ )
	{
		g[ i ].first = x[ i ][ 5 ] / x[ i ][ 1 ];
		g[ i ].second = i;
	}

	sort( g.begin(), g.end() );

	for ( int i = 0; i < n; i++ )
	{
		int k = g[ i ].second;
		bool go = true;

		for ( int j = 0; k - j >= 0 && x[ k ][ 0 ] - x[ k ][ 2 ] <= x[ k - j ][ 0 ]; j++ )
			if ( x[ k - j ][ 4 ] - 1 == 0 )
				go = false;

		for ( int j = 1; k + j < n && x[ k ][ 0 ] + x[ k ][ 3 ] >= x[ k + j ][ 0 ]; j++ )
			if ( x[ k + j ][ 4 ] - 1 == 0 )
				go = false;

		if ( go )
		{
			for ( int j = 0; k - j >= 0 && x[ k ][ 0 ] - x[ k ][ 2 ] <= x[ k - j ][ 0 ]; j++ )
				x[ k - j ][ 4 ]--;

			for ( int j = 1; k + j < n && x[ k ][ 0 ] + x[ k ][ 3 ] >= x[ k + j ][ 0 ]; j++ )
				x[ k + j ][ 4 ]--;

			x[ k ][ 5 ] = 0;
		}
	}

	int sum = 0;
	for ( int i = 0; i < n; i++ )
		if ( x[ i ][ 5 ] != 0 )
			sum += x[ i ][ 1 ];

	out << sum << '\n';

	in.close();
	out.close();

	return 0;
}