oj.uz

답안 #1006439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1006439 2024-06-24T02:22:56 Z huutuan 건포도 (IOI09_raisins) C++14
100 / 100
 320 ms 26972 KB 
#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

# 결과 실행 시간 메모리 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