# 1402.reducing-dishes

## Statement

• Difficulty: Hard
• Tag: `贪心` `数组` `动态规划` `排序`

``````输入：satisfaction = [-1,-8,0,5,-9]

``````输入：satisfaction = [4,3,2]

``````

``````输入：satisfaction = [-1,-4,-5]

``````

``````输入：satisfaction = [-2,5,-1,0,3,-3]

``````

• `n == satisfaction.length`
• `1 <= n <= 500`
• `-10^3 <= satisfaction[i] <= 10^3`

• Link: Reducing Dishes
• Difficulty: Hard
• Tag: `Greedy` `Array` `Dynamic Programming` `Sorting`

A chef has collected data on the `satisfaction` level of his `n` dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. `time[i] * satisfaction[i]`.

Return the maximum sum of like-time coefficient that the chef can obtain after dishes preparation.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

Example 1:

``````Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.``````

Example 2:

``````Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
``````

Example 3:

``````Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.
``````

Constraints:

• `n == satisfaction.length`
• `1 <= n <= 500`
• `-1000 <= satisfaction[i] <= 1000`

## Solution

``````#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define SZ(x) int((x).size())
#define endl "\n"
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
x += y;
while (x >= Mod) x -= Mod;
while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
if (x < y)
x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
if (x > y)
x = y;
}
inline int nextInt() {
int x;
cin >> x;
return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
cin >> arg;
rd(args...);
}
#define dbg(x...)                             \
do {                                      \
cout << "\033[32;1m" << #x << " -> "; \
err(x);                               \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
cout << arg << ' ';
err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
for (auto &v : arg) cout << v << ' ';
err(args...);
}
void ptt() {
cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
cout << ' ' << arg;
ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
cout << arg;
ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
pt(args...);
}
inline ll qpow(ll base, ll n) {
assert(n >= 0);
ll res = 1;
while (n) {
if (n & 1)
res = res * base % mod;
base = base * base % mod;
n >>= 1;
}
return res;
}
int n;

vector<int> vec;

int calc(vector<int> &vec) {
sort(vec.begin(), vec.end());
int res = 0;
int cnt = 1;
for (auto &it : vec) {
res += it * cnt;
++cnt;
}
return res;
}

class Solution {
public:
int maxSatisfaction(vector<int> &satisfaction) {
vec = satisfaction;
n = SZ(vec);
sort(vec.begin(), vec.end());
vector<int> A, B;
for (auto &it : vec) {
if (it >= 0)
A.push_back(it);
else
B.push_back(it);
}
reverse(B.begin(), B.end());
int res = calc(A);
for (auto &it : B) {
A.push_back(it);
chmax(res, calc(A));
}
return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````