TopCoder SRM 605 Div1 Easy AlienAndHamburgers

問題

n個のハンバーガーがあり、それぞれ種類がtype[i], 味がtaste[i]である。
この中からエイリアンに食べさせるハンバーガーを選ぶ。
エイリアンの満足度は、食べさせたハンバーガーのうち異なるtypeが何種類あるかをY
食べさせたハンバーガーの味の合計をAとすると、Y * Aである。

得られる満足度の最大値を求めよ。

制約条件

n≦50
type[i]≦100
taste[i]の絶対値≦10000

方針

tasteが負でないハンバーガーは全部食べさせて損にならない。
tasteが負であるハンバーガーは、種類を増やすために食べさせるかもしれない。
以下tasteが負であるハンバーガーだけ考える。

同じtypeで、tasteが負でないハンバーガーがあったらそのハンバーガーは使わない。
また、同じtypeのハンバーガーのうち、使うのはtasteが一番マシなハンバーガーだけ。

なのでその種類を増やすのに使うハンバーガーの候補をリストアップして、そのうち何種類を使うか全通り試せばいい。
これは候補をtasteをマシな順にソートして、マシなほうからi個使えばいい。

ソースコード

class AlienAndHamburgers {
	public:
	int getNumber(vector <int> type, vector <int> taste) {
		
		int n = type.size();
		int types = 0, tastes = 0;
		vi nega;
		bool use[110] = {};
		
		rep(i, n){
			if(use[type[i]]) continue;
			use[type[i]] = 1;
			
			int mx = -inf;
			rep(j, n) if(type[j] == type[i]){
				
				mx = max(mx, taste[j]);
				if(taste[j] >= 0) tastes += taste[j];
			}
			if(mx >= 0) types++;
			else nega.pb(mx);
		}
		sort(all(nega), greater<int>());
		int ans = types * tastes;
		
		rep(i, nega.size()){
			types++;
			tastes += nega[i];
			ans = max(ans, types * tastes);
		}
		return ans;
	}
};