Two players alternately cut whole columns off the west and rows off the south of a p by q chessboard chocolate; compute the optimal final score difference.
Medium4Game theoryDynamic programmingNo attempts yetTime limit2sMemory limit512 MBYour family has been given a huge piece of chocolate. You ate most of it last time, so your parents invented a game that makes you and your sister split this one fairly. The chocolate is a rectangle of p×q little squares, and dark chocolate squares and white chocolate squares alternate in a chessboard pattern. You and your sister both love dark chocolate and hate white chocolate. Every dark square you obtain raises your happiness by 1, and every white square you obtain lowers your happiness by 1. The same holds for your sister.
Your parents put the rectangle on a table. You sit on the west side and your sister sits on the south side. The side of length p is parallel to the north-south line, and the side of length q is parallel to the east-west line. The north-west square is dark chocolate.
You move first, and after that the two of you alternate. On your turn you may break off any positive number of entire columns from the west side of what is left and keep them. On your sister's turn she may break off any positive number of entire rows from the south side of what is left and keep them. The game ends when no chocolate is left.
Your score is your happiness minus your sister's happiness. You want that score to be as large as possible and your sister wants it to be as small as possible. Your sister is very smart and always plays optimally.
A game on a 3×4 rectangle can go like this. You break off 2 columns and obtain 3 dark squares and 3 white squares, so your happiness does not change. Your sister breaks off 1 row and obtains 1 dark square and 1 white square, so her happiness does not change either. You break off a single column and again obtain 1 dark square and 1 white square. Your sister breaks off one row, which is a single dark square, so her happiness goes up by 1. You take the last square, which is white, so your happiness goes down by 1. Your score is −1−1=−2. The moves in this example are not necessarily optimal.

The first line contains the height p and the width q of the chocolate rectangle (1≤p≤100, 1≤q≤100).
Print the largest possible value of your happiness minus your sister's happiness when both of you play optimally.