Cod sursa(job #3335814)

Utilizator vladimir.gavris.1Gavris Mihai Vladimir vladimir.gavris.1 Data 23 ianuarie 2026 17:36:21
Problema Tablete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#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;
}