Submission #856143

#TimeUsernameProblemLanguageResultExecution timeMemory
856143IrateRaisins (IOI09_raisins)C++14
100 / 100
434 ms29272 KiB
#include<cstdio> using namespace std; const int mxN = 52; int min(int a, int b){ if(a > b)return b; return a; } int grid[mxN][mxN], pref[mxN][mxN], dp[mxN][mxN][mxN][mxN]; int rec(int x1, int y1, int x2, int y2){ int sum = pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1], res = 1e9; if(x1 == x2 && y1 == y2)return 0; if(dp[x1][y1][x2][y2] != -1)return dp[x1][y1][x2][y2]; for(int i = x1 + 1;i <= x2;++i){ res = min(res, sum + rec(i, y1, x2, y2) + rec(x1, y1, i - 1, y2)); } for(int i = y1 + 1;i <= y2;++i){ res = min(res, sum + rec(x1, y1, x2, i - 1) + rec(x1, i, x2, y2)); } return dp[x1][y1][x2][y2] = res; } int main(){ int n, m; scanf("%d %d", &n, &m); for(int i = 0;i < mxN;++i){ for(int j = 0;j < mxN;++j){ for(int k = 0;k < mxN;++k){ for(int l = 0;l < mxN;++l){ dp[i][j][k][l] = -1; } } } } for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ scanf("%d", &grid[i][j]); pref[i][j] = pref[i - 1][j] + pref[i][j - 1] + grid[i][j] - pref[i - 1][j - 1]; } } printf("%d", rec(1, 1, n, m)); }

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
raisins.cpp:35:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |             scanf("%d", &grid[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...