CFR Educational 1 E. Chocolate Bar ( DP )

Problem - E - Codeforces
dp[ i ][ j ][ k ]: Having an i * j chocolate bar, the minimum cost required to take a piece of area k
${ \displaystyle Disregarding\ negative\ index,\ we\ have\\ dp(\ i,\ j,\ k\ ) = min\{ min_{c=1}^{i-1}\ min\{\ dp(\ i - c,\ j,\ k - j * c\ ) + j * j,\ dp(\ i - c,\ j,\ k\ ) + j * j\ \},\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ min_{c=1}^{j-1}\ min\{\ dp(\ i,\ j - c,\ k - i * c\ ) + i * i,\ dp(\ i,\ j - c,\ k\ ) + i * i\ \} \} }$
which we enumerate all the possible cut lines and make decisions whether taking it or not

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXT = 40910 + 2;
const int MAXN = 30 + 2;
const int MAXM = 30 + 2;
const int MAXK = 50 + 2;

void upmin(int &x, int v){ if( x > v ) x = v; }

int n, m, k;

// dp[ i ][ j ][ k ]: minimum cost to take area k from choc i * j
int dp[ MAXN ][ MAXM ][ MAXK ];

void preSolve(){
    memset( dp, INF, sizeof(dp) );
    for(int i = 1; i < MAXN; ++i)
        for(int j = 1; j < MAXM; ++j)
            if( i * j < MAXK )
                dp[ i ][ j ][ i * j ] = 0;
    for(int i = 1; i < MAXN; ++i)
        for(int j = 1; j < MAXM; ++j)
            for(int x = 1; x < MAXK; ++x){
                for(int c = 1; c < i; ++c){ // discard
                    upmin( dp[ i ][ j ][ x ], dp[ i - c ][ j ][ x ] + j * j );
                    if( x - c * j > 0 ) // take
                        upmin( dp[ i ][ j ][ x ], dp[ i - c ][ j ][ x - c * j ] + j * j );
                }
                for(int c = 1; c < j; ++c){
                    upmin( dp[ i ][ j ][ x ], dp[ i ][ j - c ][ x ] + i * i );
                    if( x - c * i > 0 )
                        upmin( dp[ i ][ j ][ x ], dp[ i ][ j - c ][ x - c * i ] + i * i );
                }
            }
}

int main(){
    preSolve();
    int T; scanf("%d", &T);
    while( T-- ){
        scanf("%d%d%d", &n, &m, &k);
        printf("%d\n", dp[ n ][ m ][ k ]);
    }
    return 0;
}