# CFR 613 B. Skills ( Binary Search )

Problem - B - Codeforces

N ≤ 1e5
A ≤ 1e9
Cf, Cm ≤ 1000
M ≤ 1e15

O( N lg N ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

template< class T1, class T2 >
bool upmax( T1 &x, T2 v ){
if( x >= v ) return 0;
x = v; return 1;
}

const int MAXN = ( int ) 1e5;

int N, A, Cf, Cm;
long long M;
int a[ MAXN ];
long long lpfx[ MAXN + 1 ];
long long gpfx[ MAXN + 1 ];
int lord[ MAXN ];
int gord[ MAXN ];

signed main(){
ios::sync_with_stdio( 0 );
{
cin >> N >> A >> Cf >> Cm >> M;
for( int i = 0; i < N; ++i ){
cin >> a[ i ];
gord[ i ] = i;
lord[ i ] = i;
}
sort( lord, lord + N, [ & ]( int i, int j ){ return a[ i ] < a[ j ]; } );
sort( gord, gord + N, [ & ]( int i, int j ){ return a[ i ] > a[ j ]; } );
for( int i = 0; i < N; ++i ){
lpfx[ i + 1 ] = lpfx[ i ] + a[ lord[ i ] ];
gpfx[ i + 1 ] = gpfx[ i ] + a[ gord[ i ] ];
}
}
{
long long maxv = -1;
int bestg, bestl, bestp;
for( int i = 0; i <= N; ++i ){
long long value = 1LL * i * Cf;
long long cost = 1LL * i * A - gpfx[ i ];
if( cost > M ) continue;
int mins, minf; // maximum threshold of minimum, skills involved in this update
for( int lb = 0, rb = A; lb <= rb; ){
int mid = lb + rb >> 1;
int f = N - i; // !!!!!!
{
for( int lb = 0, rb = N - i - 1; lb <= rb; ){
int m = lb + rb >> 1;
if( a[ lord[ m ] ] >= mid ){
f = m;
rb = m - 1;
} else{
lb = m + 1;
}
}
}
if( cost + 1LL * f * mid - lpfx[ f ] <= M ){
mins = mid;
minf = f;
lb = mid + 1;
} else{
rb = mid - 1;
}
}
if( upmax( maxv, value + 1LL * mins * Cm ) ){
bestg = i;
bestl = mins;
bestp = minf;
}
}
cout << maxv << endl;
vector< int > ans( N );
for( int i = 0; i < N; ++i ){
ans[ i ] = a[ i ];
}
for( int i = 0; i < bestg; ++i ){
ans[ gord[ i ] ] = A;
}
for( int i = 0; i < bestp; ++i ){
ans[ lord[ i ] ] = bestl;
}
for( int i = 0; i < N; ++i ){
cout << ans[ i ] << " \n"[ i + 1 == N ];
}
}
return 0;
}
```