読者です 読者をやめる 読者になる 読者になる

SRM406 Div1Easy SymmetricPie

解法
与えられたデータを用いたとき、最大の対象な分割のための線分の数を求める。
素数が8までなので、next_permutation で回して累積和を取り+50となる要素のペアを数え上げる。

#define ALL(x) (x).begin(), (x).end()
class SymmetricPie {
public:
  int getLines(vector <int> dogs) {
    
    sort(ALL(dogs));
    int N = dogs.size();
    int ans = 0;
    do {
      vector<int> sum(N+1);
      for(int i=0; i<dogs.size(); i++) {
        sum[i+1] = sum[i] + dogs[i];
      }
    
      int cnt = 0;
      for(int i=0; i<N; i++) {
        if(find(ALL(sum), sum[i]+50) < sum.end()-1) {
          cnt ++;
        }
      }
      ans = max(ans, cnt);
    } while(next_permutation(ALL(dogs)));
    
    return ans;
  }
};