SRM605 div1 Easy AlienAndHamburgers

メモ

tasteが正なら絶対食べた方が良い

tasteが負の場合はそのハンバーガーを食べることで種類が増えるなら、食べるとjoiを大きくできる可能性がある

tasteが負のハンバーガーしかない種類については、tasteが一番大きいハンバーガーだけを食べるか食べないか考えれば良い（種類を増やすならtasteが一番大きいのを選んだ方が良い）

tasteが負のハンバーガーしかない種類ごとに、食べるか食べないかの1つのハンバーガーの候補を保存しとく

それらの候補の中でtasteが大きいものから順にjoiが大きくなる間食べれば良い（種類を増やすならtasteが大きいものから食べた方が良い）

コード

class AlienAndHamburgers {
public:
  int getNumber(vector <int> type, vector <int> taste) {
    int n = type.size();
    bool plus[101]; CLR(plus);
    // プラスがあるタイプかどうか
    FOR(i,0,n) if(taste[i] >= 0) plus[type[i]] = true;
    bool usedType[101]; CLR(usedType);
    int Y = 0, A = 0;
    vector<int> v[101];
    FOR(i,0,n) {
      // +ならくう
      if(taste[i] >= 0) {
        if(!usedType[type[i]]) {
          Y++;
          usedType[type[i]] = true;
        }
        A += taste[i];
      }
      // tasteがマイナスだけどtype数増えるからスコア上がるかも
      else if(!plus[type[i]]) {
        v[type[i]].push_back(taste[i]);
      }
    }
    vector<int> vv;
    FOR(i,0,101) {
      if(v[i].size() > 0) {
        sort(v[i].rbegin(), v[i].rend());
        vv.push_back(v[i][0]);
      }
    }
    sort(vv.rbegin(), vv.rend());
    int ret = Y * A;
    FOR(i,0,vv.size()) {
      Y++;
      A += vv[i];
      ret = max(ret, Y * A);
    }
    return ret;
  }
};

メモが雑...