#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
#define long long long
#define v vector
#define rep(i,a,b) for(int i=a; i<b; i++)
void setIO(string name, int submit) {
if (submit) {
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
const int MAXN=52;
int arr[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
int N, M;
int recurse(int ix, int iy, int jx, int jy){
if(jx-ix==0 && jy-iy==0) {
dp[ix][iy][jx][jy]=0;
}
if(dp[ix][iy][jx][jy]!=-1){
int best=1<<30;
for(int row= iy+1; row<=jy; row++){
best= min(best, recurse(ix, row, jx, jy)+recurse(ix, iy, jx, row-1));
}
for(int col= ix+1; col<=jx; col++){
best= min(best, recurse(col, iy, jx, jy)+ recurse(ix, iy, col-1, jy));
}
int base=arr[jx][jy]-arr[ix-1][jy]-arr[jx][iy-1]+arr[ix-1][iy-1];
dp[ix][iy][jx][jy]= best+base;
}
return dp[ix][iy][jx][jy];
}
int main() {
setIO("", 0);
cin >>N>>M;
rep(i,1,N+1){
rep(j,1,M+1){
cin>> arr[i][j];
arr[i][j]+=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];
}
}
rep(i,1,N+1){
rep(j,1,M+1){
rep(k,1,N+1){
rep(l,1,M+1){
dp[i][j][k][l]=-1;
}
}
}
}
cout << recurse(1,1,N,M)<< endl;
return 0;
}
Compilation message
raisins.cpp: In function 'void setIO(std::string, int)':
raisins.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
13 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
raisins.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
14 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
1024 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
1152 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 10 |
Incorrect |
4 ms |
5888 KB |
Output isn't correct |
| 11 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 12 |
Incorrect |
7 ms |
10624 KB |
Output isn't correct |
| 13 |
Incorrect |
8 ms |
13312 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
6144 KB |
Output isn't correct |
| 15 |
Incorrect |
8 ms |
14464 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
4992 KB |
Output isn't correct |
| 17 |
Incorrect |
6 ms |
9728 KB |
Output isn't correct |
| 18 |
Incorrect |
14 ms |
20864 KB |
Output isn't correct |
| 19 |
Incorrect |
17 ms |
25344 KB |
Output isn't correct |
| 20 |
Incorrect |
18 ms |
27008 KB |
Output isn't correct |
