SRM453.5 Div1 Medium

450

bool is_planar(int v, int e)
{
  if( 3 <= v )return e <= 3 * v - 6;
  if( e == 0 )return true;
  return e < (v - 1) * v;
}

class PlanarGraphShop {
public:
  int bestCount(int N) {

    const int inf = 1 << 24;
    const int T = N + 1;
    int t[T];
    fill( t, t + T, inf );
    t[0] = 0;

    for(int i=0; i<N; ++i){
      for(int v=1; i+v*v*v < T; ++v){
        for(int e=0; i+v*v*v+e*e < T; ++e){
          if( !is_planar(v, e) )continue;
          int j = v * v * v + e * e + i;
          t[j] = min( t[j], t[i] + 1 );
        }
      }
    }

    return t[N];
  }
};