CSES – Rectangle Cutting

#include<bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 505;
int a,b;
int dp[maxn][maxn];
//
int solve(int a,int b){
    if(a > b) swap(a,b);
    if(dp[a][b] != 1e18) return dp[a][b];
    if(a == 1) return b-1;
    if(a == b) return 0;
    for(int i=1;i<b;i++){
        dp[a][b] = min(dp[a][b], solve(a,i)+solve(a,b-i)+1);
    }
    for(int i=1;i<a;i++){
        dp[a][b] = min(dp[a][b], solve(i,b)+solve(a-i,b)+1);
    }
    return dp[a][b];
}
signed main(){
    fastio;
    cin>>a>>b;
    for(int i=0;i<maxn;i++) fill(dp[i],dp[i]+maxn,(int)1e18);
    cout<<solve(a,b)<<"\n";
    return 0;
}