SRM314Div2

250

class MooingCows {
public:
  int dissatisfaction(vector <string> f) {
    int r = 1 << 22;
    for(int i=0; i<f.size(); ++i){
      for(int j=0; j<f[i].size(); ++j){
        if(f[i][j] == '.')continue;
        int sum = 0;
        for(int k=0; k<f.size(); ++k){
          for(int l=0; l<f[k].size(); ++l){
            if(f[k][l] == '.')continue;
            sum += (i-k) * (i-k) + (j-l) * (j-l);
          }
        }
        r = min(r, sum);
      }
    }
    return r;
  }
}; 

500

class StandInLine {
public:
  vector <int> reconstruct(vector <int> l) {
    vector <int> r;
    for(int i=0; i<l.size(); ++i){
      r.push_back(i + 1);
    }
    do{
      bool flg = true;
      for(int i=0; i<r.size(); ++i){
        int cnt = 0;
        for(int j=0; j<i; ++j){
          cnt += r[i] < r[j];
        }
        flg = flg && cnt == l[r[i]-1];
      }
      if(flg)break;
    }while(next_permutation(r.begin(), r.end()));
    return r;
  }
};

1000

map<int, double> t[6];

class GrasslandFencer {
public:
  double heron(double A, double B, double C){
    double p = (A+B+C)/2.0;
    return sqrt(p*(p-A)*(p-B)*(p-C));
  }
  double rec(int s, vector<int> f, int d){
    if( t[d].find(s) != t[d].end() )return t[d][s];
    double mx = 0;
    const int size = f.size();
    for(int i=0; i<size; ++i){
      if(s & (1 << i))continue;
      for(int j=i+1; j<size; ++j){
        if(s & (1 << j))continue;
        for(int k=j+1; k<size; ++k){
          if(s & (1 << k))continue;
          if(f[i] + f[j] <= f[k])continue;
          int bit = s | (1 << i) | (1 << j) | (1 << k);
          mx = max(mx, rec(bit, f, d + 1) + heron(f[i], f[j], f[k]));
        }
      }
    }
    return t[d][s] = mx;
  }
  double maximalFencedArea(vector <int> f) {
    fill(t, t + 6, map<int, double>());
    sort(f.begin(), f.end());
    return rec(0, f, 0);
  }
};