613B - Skills - CodeForces Solution

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i = a;i<=b;i++)
#define per(i,a,b) for(int i = b;i>=a;i--)
#define clean(a,c) memset(a,c,sizeof(a))
const int maxn = 1e5+5;//,maxm = 2e5+5;
typedef long long ll;
typedef pair<int,int> pii;
pii a[maxn];
ll pre[maxn];
int temp[maxn];

int main()
{
    int n,cf,cm,maxa;
    ll m;
    int cnt = 0;
    scanf("%d%d%d%d%I64d",&n,&maxa,&cf,&cm,&m);
    rep(i,1,n)
    {
        int tmp;
        scanf("%d",&tmp);
        a[i] = {tmp,i};
    }
    sort(a+1,a+n+1);
    rep(i,1,n)
        pre[i] = pre[i-1]+a[i].first;
    int minn = pre[1];
    int cntt;
    per(i,1,n)
    {
        cntt = n-i;
        ll cost = 1ll*cntt * maxa - pre[n] + pre[i];
        int l = 1,r = i;
        int tmp = 0;
        while(l<=r)
        {
            int mid = (l + r)>>1;
            if(1ll*mid * a[mid].first - pre[mid] + cost <= m)
            {
                tmp = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        if(!tmp)
            break;
        int tmpminn = a[tmp].first;
        tmpminn = min((ll)maxa,(m - (1ll*tmp * a[tmp].first - pre[tmp] + cost)) / tmp + tmpminn);
        if(tmpminn == maxa)
            cntt = n;
        if(1ll*tmpminn * cm + 1ll*cntt * cf > 1ll*minn * cm + 1ll*cnt * cf)
            minn = tmpminn,cnt = cntt;
    }
    printf("%I64d\n",1ll*minn * cm + 1ll*cnt * cf);
    rep(i,1,n)
    {
        if(n-i < cnt)
            temp[a[i].second] = maxa;
        else
            temp[a[i].second] = max(minn,a[i].first);
    }
    rep(i,1,n)
        printf("%d%c",temp[i],i != n ? ' ':'\n');


}