SRM547 Div1 Medium(500) RectangularSum

RectangularSum

Subtableの左上の数字をs、幅をw、高さをhとすると、合計は

S = (1/2)wh( (w-1)+2s+width(h-1) )。

よって、2Sはwhを約数に持つ。2Sの約数の個数は最悪ケース（S=963761198400）でも、7680個なので、wとhの全ての組合わせについて、sを求め、subtableがtable内にあるかを調べる。あまり実行時間に余裕は無いので、最初に約数を求めておかないと間に合わなかった。

#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

class RectangularSum{public:
long long minimalArea( int height, int width, long long S )
{
    //  2Sの約数を求める
    vector<long long> D;
    for ( long long d=1; d*d<=2*S; d++ )
    if ( 2*S%d==0 )
        D.push_back(d),
        D.push_back(2*S/d);
    sort(D.begin(),D.end());

    long long ans = LLONG_MAX;
    for ( int i=0; i<(int)D.size() && D[i]<=height; i++ )
    for ( int j=0; j<(int)D.size() && D[j]<=width;  j++ )
    if ( 2*S%(D[i]*D[j])==0 )
    {
        long long h = D[i];
        long long w = D[j];
        long long s = 2*S/w/h - (w-1) - width*(h-1);

        if ( 0<=s && s%2==0 )
        {
            s /= 2;

            if ( s%width+w-1 < width &&
                 s/width+h-1 < height )
            {
                ans = min(ans,h*w);
            }
        }
    }

    return ans<LLONG_MAX ? ans : -1;

}};