naoya_t@topcoder

SRM362 Div1 Easy: MaximizeSquares

過去問, 練習 | 01:49 |

Failed System Test...

• 使える点の数から、考えられる幅と高さについて全て試す法
• 単純なミス(コメントアウトした箇所)

class MaximizeSquares {
 public:
  int squareCount(int N) {
    if(N<4) return 0;
    int wmin=(int)sqrt(N),wmax=N/2;
    int cmax=wmax-1;
    for(int w=wmin;w<=wmax;w++){
      int c=0;
      int h0=N/w;
      int w0=N-w*h0;
      if(w0==1) w0=0;
      int h=h0+((w0==0)?0:1);
      int rmax=min(w,h);
      for(int r=1;r<=rmax;r++){
//      if(w>=r && h0>=r) c += (w-r)*(h0-r);
//      if(w0>=r && h>=r) c += (w0-r);
        if(w-1>=r && h0-1>=r) c += (w-r)*(h0-r);
        if(w0-1>=r && h-1>=r) c += (w0-r);
      }
      cmax = max(cmax,c);
    }
    return cmax;
  }
};