Submission #1006439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006439		huutuan	Raisins (IOI09_raisins)	C++14	100 / 100	320 ms	26972 KiB

raisins

#include <bits/stdc++.h>

using namespace std;

const int N=51;
int f[N][N][N][N], pf[N][N], a[N][N], n, m;

int dp(int x1, int y1, int x2, int y2){
   if (f[x1][y1][x2][y2]!=-1) return f[x1][y1][x2][y2];
   if (x1==x2 && y1==y2) return f[x1][y1][x2][y2]=0;
   int sum=pf[x2][y2]-pf[x1-1][y2]-pf[x2][y1-1]+pf[x1-1][y1-1];
   int ans=1e9;
   for (int x=x1; x<x2; ++x){
      ans=min(ans, dp(x1, y1, x, y2)+dp(x+1, y1, x2, y2)+sum);
   }
   for (int y=y1; y<y2; ++y){
      ans=min(ans, dp(x1, y1, x2, y)+dp(x1, y+1, x2, y2)+sum);
   }
   return f[x1][y1][x2][y2]=ans;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j){
      cin >> a[i][j];
      pf[i][j]=pf[i-1][j]+pf[i][j-1]-pf[i-1][j-1]+a[i][j];
   }
   memset(f, -1, sizeof f);
   cout << dp(1, 1, n, m) << '\n';
   return 0;
}

• Subtask 1: 100 / 100