naoya_t@topcoder

SRM406 Div1 Easy: SymmetricPie

過去問, 練習 | 18:04 |

next_permutationを使ってBrute Force

class SymmetricPie {
public:
  int getLines(vector<int> dogs) {
    int N=sz(dogs);
    sort(all(dogs));
    int maxcnt=0;
    while(1) {
      int cnt=0;
      vector<int> ac(N+1,0); ac[0]=0;
      for(int i=0;i<N;i++) ac[i+1]=ac[i]+dogs[i];
      for(int i=0;i<N;i++) {
        if (ac[i]<50){
          for(int j=i+1;j<=N;j++) {
            if (ac[j]-ac[i]==50) cnt++;
          }
        }
      }
      if (maxcnt<cnt) maxcnt=cnt;
      if (!next_permutation(all(dogs))) break;
    }
    return maxcnt;
  }
};