CFR 557 C. Arthur and Table ( DP )

Problem - 557C - Codeforces

```const int MAXL = ( int ) 1e5;
const int MAXD = 200;

int N;
vi L;
vi D;

void init(){
cin >> N;
L = D = vi( N );
for( int i = 0; i < N; ++i )
cin >> L[ i ];
for( int i = 0; i < N; ++i )
cin >> D[ i ];
}

vp ld; // pii( L, D )
vi lcnt; // count of L
vi plcnt; // prefix sum of count of L, [ 1, L )
vvi _d_l_cnt; // count of ( L, D )
vvi p_d_l_cnt; // under fixed D, prefix sum of count of L, [ D ][ 1, L )

void preprocess(){
ld = vp( N );
for( int i = 0; i < N; ++i )
ld[ i ] = pii( L[ i ], D[ i ] );
sort( ld.begin(), ld.end() );
lcnt = vi( MAXL + 1 );
for( int i = 0; i < N; ++i )
++lcnt[ L[ i ] ];
plcnt = vi( MAXL + 1 );
for( int i = 0; i < MAXL; ++i )
plcnt[ i + 1 ] = plcnt[ i ] + lcnt[ i ];
_d_l_cnt = vvi( MAXD + 1, vi( MAXL + 1 ) );
for( int i = 0; i < N; ++i )
++_d_l_cnt[ D[ i ] ][ L[ i ] ];
p_d_l_cnt = vvi( MAXD + 1, vi( MAXL + 1 ) );
for( int i = 1; i <= MAXD; ++i )
for( int j = 0; j < MAXL; ++j )
p_d_l_cnt[ i ][ j + 1 ] = p_d_l_cnt[ i ][ j ] + _d_l_cnt[ i ][ j ];
}

void solve(){
int ans = INF;
for( int i = N - 1, ds = 0; 0 <= i; ds += ld[ i ].second, --i ){ // ds : sum of D for larger Ls
if( i + 1 < N and ld[ i ].first == ld[ i + 1 ].second ) // if same L, then it had been considered, thus skip
continue;
int chcnt = 0, cost = 0, rmgol = max( 0, plcnt[ ld[ i ].first ] - ( lcnt[ ld[ i ].first ] - 1 ) ); // remove goal = count of smaller - ( count of cur - 1 )
for( int j = 1; j <= MAXD; ++j ){
chcnt += p_d_l_cnt[ j ][ ld[ i ].first ];
cost += p_d_l_cnt[ j ][ ld[ i ].first ] * j;
if( chcnt >= rmgol ){
cost -= ( chcnt - rmgol ) * j;
chcnt = rmgol;
break;
}
}
if( chcnt == rmgol )
upmin( ans, cost + ds );
}
cout << ans << endl;
}
```