Submission #3791009

---

Source Code Expand

using namespace std ;
#include <bits/stdc++.h> // #7th-Polygon
#define TASKNAME "PHIDIAS"
inline int Minimize(int& A , int B) { return A = min(A , B) ; }

const int N = 600 ;

int dp[N + 7][N + 7] ;

int GetDP(int width , int height)
{
    if (dp[width][height] != -1) return dp[width][height] ;
    dp[width][height] = width * height ;

    for (int k = 1 ; k <= (width >> 1) ; ++k) if (dp[width][height] != 0)
        Minimize(dp[width][height] , GetDP(k , height) + GetDP(width - k , height)) ;
    for (int k = 1 ; k <= (height >> 1) ; ++k) if (dp[width][height] != 0)
        Minimize(dp[width][height] , GetDP(width , k) + GetDP(width , height - k)) ;
    return dp[width][height] ;
}

int main()
{
    //freopen(TASKNAME".inp" , "r" , stdin) ;
    //freopen(TASKNAME".out" , "w" , stdout) ;
    ios::sync_with_stdio(false) ;
    cout.tie(nullptr) ;
    cin.tie(nullptr) ;

    int TestCase ;
    cin >> TestCase ;

    while (TestCase--)
    {
        int width , height , n ;
        cin >> width >> height >> n ;

        memset(dp , -1 , sizeof dp) ;
        for (int i = 1 ; i <= n ; ++i)
        {
            int curr_width , curr_height ;
            cin >> curr_width >> curr_height ;
            dp[curr_width][curr_height] = false ;
        }

        cout << GetDP(width , height) << "\n" ;
    }

    cerr << "Executed time: " << clock() << " ms\n" ;
    return 0 ;
}

Submission Info

Judge Result