SRM Div1 605 Easy AlienAndHamburgers

問題

ハンバーガーが複数あり、種類と味の良さがtype[i], taste[i]で与えられる。同じ種類のハンバーガが異なる味の良さを持つことはある。
食べたハンバーガーの種類数　×　食べたハンバーガーの味の良さの合計　が最大になるようにハンバーガーを選んで食べた時にこの最大値はいくつか？

やりかた

（１）味の良さが0以上のハンバーガーはすべて食べる。なぜなら種類数が増えることはあれ減りはしないし、味の良さの合計は増えることはあれ減りはしないからである。

問題は（２）味の良さが負のハンバーガーである。
ただ、すでに食べたことのあるハンバーガーは食べない。種類数が増えず、合計が下がるからである。
食べるべきかもしれないのは味が負で（１）で食べていないもの。そしてこのようなハンバーガーが各種複数あるとして、食べてもよさそうなのは各種とも味の値が最も大きいハンバーガー一つずつである。なぜなら一番大きい物のほうが食べても味の合計を下げる影響を最も小さくしながら、種類数を増やせるからである。
こうして味が負で、（１）で食べていない種類で、同種類のハンバーガー中最も大きい味の値を持つハンバーガーを列挙する。このハンバーガーを更に値が大きい順から（１）で求めた値に組み入れて計算していき、最大値を計算すればいい。

以下ソース。

class AlienAndHamburgers {
public:
  int getNumber(vector <int> type, vector <int> taste) {
    int result = 0;
    int N = type.size();

    vector<pair<int, int> > P;
    set<int> s;
    
    map<int, int> nega;//（１）で食べていないハンバーガーの種類と、その種類中の味の最大値
    vector<int> best_negative;//↑における最大値を列挙したもの
    int sum = 0;
    for(int i = 0; i < N; i++){
      P.push_back(make_pair(type[i], taste[i]));
    }

    sort(ALL(P));
    for(int i = 0; i < N; i++){
      if(P[i].second >= 0){
	s.insert(P[i].first);
	sum += P[i].second;
      }
    }
    for(int i = 0; i < N; i++){
      if(s.find(P[i].first) == s.end()){
	if(nega.count(P[i].first) == 0){
	  nega[P[i].first] = P[i].second;
	}else{
	  nega[P[i].first] = max(nega[P[i].first], P[i].second);
	}
      }
    }
    
    result = max(0, (int)s.size() * sum);
    for(map<int, int>::iterator it = nega.begin(); 
　　　it != nega.end(); it++){
      best_negative.push_back(it -> second);
    }

    sort(ALL(best_negative), greater<int>());
    for(int i = 0; i < (int)best_negative.size(); i++){
      sum += best_negative[i];
      result = max(result, sum * (int)(s.size() + i + 1));
    }
    return result;
  }

間抜けなバグをぶちこんでしまい。バグ取りが間に合わず落とした。反省。