解法
縦と横については、向きを入れ替えて同じことを考えればよいので、とりあえず縦と横を固定した状態で考えます。
チョコレートを3つに分けるには、まず2つに分け、そのうち片方をまた2つに分ける、というようにするしかありません。
ので、まずはチョコレートを2つに分けます。今回は、縦の長さhをa:bで分けることを考えます。
すると、1つのチョコレートの面積が決まります。a×wです。
残ったb×wの面積のチョコレートを決めます。これをできるだけ半分に分けたいです。
bかwのどちらかが偶数であれば、面積を(b×w)/2で分割することができます。
そうでなかった場合、(b×w)/2と(b×w)/2+bもしくは(b×w)/2と(b×w)/2+wで分割するしかありません。
あとは、a×wと、残りの2つの面積のうち、最大値と最小値の差が最小になるようなaを全探索で求めれば答えとなります。wとhを入れ替えて調べるのも忘れないようにしましょう。
