Pagini recente » Cod sursa (job #1596653) | Cod sursa (job #2774906) | Cod sursa (job #2714133) | Cod sursa (job #1317019) | Cod sursa (job #993060)
Cod sursa(job #993060)
#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;
}