Pagini recente » Cod sursa (job #3317405) | Cod sursa (job #3339370) | Cod sursa (job #3345080) | Cod sursa (job #3351923) | Cod sursa (job #3335814)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in( "pitici4.in" );
ofstream out( "pitici4.out" );
#define MAXN 200000
#define MAXCOORD 1000000
struct afirm
{
int left, right;
};
afirm v[ MAXN + 1 ];
int dp[ MAXN + 1 ];
int n;
bool compare_left( afirm a, afirm b )
{
if( a.left == b.left ) return a.right < b.right;
return a.left < b.left;
}
void solve( )
{
in >> n;
for( int i = 1; i <= n; i++ )
{
in >> v[ i ].right >> v[ i ].left;
}
std::sort( v + 1, v + n + 1, compare_left );
int current = 1;
for( int i = 0; i < n; i++ )
{
dp[ i + 1 ] = std::max( dp[ i + 1 ], dp[ i ] );
while( current <= n && v[ current ].left == i )
{
int counter = 0, lak = v[ current ].right;
while( v[ current ].left == i && v[ current ].right == lak )
{
current++; counter++;
}
int add = std::min( counter, n - ( i + lak ) );
dp[ n - lak ] = std::max( dp[ n - lak ], dp[ i ] + add );
}
}
out << dp[ n ];
}
int main()
{
solve( );
return 0;
}