Score : 400 points

Problem Statement

There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.

Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize Smax - Smin, where Smax is the area (the number of blocks contained) of the largest piece, and Smin is the area of the smallest piece. Find the minimum possible value of Smax−Smin.

Constraints

• 2≤H,W≤105

H W

Sample Input 1

3 5

Sample Output 1

0

In the division below, Smax−Smin=5−5=0.

Sample Input 2

4 5

Sample Output 2

2

In the division below, Smax−Smin=8−6=2.

Sample Input 3

5 5

Sample Output 3

4

In the division below, Smax−Smin=10−6=4.

Sample Input 4

100000 2

Sample Output 4

1

Sample Input 5

100000 100000

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define INF (1LL<<62)

 LL slv(LL x,LL y,LL s)

 {

     LL X = x/,Y = y/;

     return min (

         max( max(abs(X*y-s),abs((x-X)*y-s)), abs(X*y-(x-X)*y) ),

         max( max(abs(x*Y-s),abs((y-Y)*x-s)), abs(Y*x-(y-Y)*x) )

     );

 }

 int main()

 {

     LL h,w;

     cin>>h>>w;

     LL ans = INF;

     for (int i=;i<=h;i++)

         ans = min (ans,slv(h-i,w,i*w));

     for (int i=;i<=w;i++)

         ans = min (ans, slv(w-i,h,i*h));

     cout<<ans<<endl;

     return ;

 }