# Skills

## 题目描述

Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly $n$ skills. Each skill is represented by a non-negative integer $a_i$ — the current skill level. All skills have the same maximum level $A$.
Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:

• The number of skills that a character has perfected (i.e., such that $a_i=A$), multiplied by coefficient $c_f$.
• The minimum skill level among all skills ($\min(a_i)$), multiplied by coefficient $c_m$.

Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by $1$ (if it’s not equal to $A$ yet). Help him spend his money in order to achieve the maximum possible value of the Force.

## 代码

#include <iostream>
#include <algorithm>
using namespace std;
struct skill {
long long a, id;
} s[100002];
bool cmp1(skill a, skill b) { return a.a < b.a; }
bool cmp2(skill a, skill b) { return a.id < b.id; }
long long n, A, cf, cm, m, ans, pnt, cnt, rec[3], pre[100002], suf[100002];
int main()
{
cin >> n >> A >> cf >> cm >> m;
for (int i = 1; i <= n; ++i) {
cin >> s[i].a; s[i].id = i;
}
sort(s + 1, s + n + 1, cmp1);
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + s[i].a;
for (int i = n; i; --i) suf[i] = suf[i + 1] + s[i].a;
cnt = 0, pnt = n, rec[0] = n + 1;
while (pnt > 0 && (n - pnt + 1) * A - suf[pnt] <= m) --pnt;
for (++pnt; pnt <= n + 1; ++pnt) {
long long rem = m - (n - pnt + 1) * A + suf[pnt];
while (cnt < pnt && s[cnt].a * cnt - pre[cnt] <= rem) ++cnt; --cnt;
if (cnt) (rem -= s[cnt].a * cnt - pre[cnt]) /= cnt; else rem = 1e18;
if (ans < (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm) {
ans = (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm;
rec[0] = pnt, rec[1] = cnt, rec[2] = min((s[cnt].a + rem), A);
}
}
for (int i = 1; i <= rec[1]; ++i) s[i].a = rec[2];
for (int i = rec[0]; i <= n; ++i) s[i].a = A;
sort(s + 1, s + n + 1, cmp2);
cout << ans << endl;
for (int i = 1; i <= n; ++i) cout << s[i].a << ' ';
cout << endl;
return 0;
}


418 I'm a teapot