Submission #330297

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

int n,m,j,k,i,l;
int A[1500][3];
int dp[1500][15000];

int f(int x,int y){

   int i;

   if(dp[x][y] != -1)
      return dp[x][y];

   dp[x][y] = 0;

   if(!x || !y)
      return dp[x][y];

   for(i=1 ; i<=k ; i++)

      if(A[i][0] > x || A[i][1] > y)
         continue;

      else
         dp[x][y] = max(dp[x][y],max(f(x-A[i][0],A[i][1]) + f(x,y-A[i][1]) , f(x-A[i][0],y) + f(A[i][0],y-A[i][1]) ) + A[i][0]*A[i][1]);

   return dp[x][y];
}

int main(){

   memset(dp,-1,sizeof dp);

   cin >> n >> m >> k;

   for(i=1 ; i<=k ; i++)
      cin >> A[i][0] >> A[i][1];

   cout << n*m - f(n,m);

   return 0;
}

Submission Info

Judge Result