Submission #1006439

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1006439	2024-06-24T02:22:56 Z	huutuan	Raisins (IOI09_raisins)	C++14	100 / 100	320 ms	26972 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	26716 KB	Output is correct
2	Correct	4 ms	26748 KB	Output is correct
3	Correct	3 ms	26716 KB	Output is correct
4	Correct	3 ms	26716 KB	Output is correct
5	Correct	3 ms	26968 KB	Output is correct
6	Correct	3 ms	26716 KB	Output is correct
7	Correct	3 ms	26716 KB	Output is correct
8	Correct	8 ms	26952 KB	Output is correct
9	Correct	11 ms	26716 KB	Output is correct
10	Correct	15 ms	26716 KB	Output is correct
11	Correct	14 ms	26784 KB	Output is correct
12	Correct	39 ms	26716 KB	Output is correct
13	Correct	62 ms	26716 KB	Output is correct
14	Correct	23 ms	26716 KB	Output is correct
15	Correct	76 ms	26716 KB	Output is correct
16	Correct	9 ms	26716 KB	Output is correct
17	Correct	38 ms	26716 KB	Output is correct
18	Correct	182 ms	26952 KB	Output is correct
19	Correct	298 ms	26972 KB	Output is correct
20	Correct	320 ms	26972 KB	Output is correct