제출 #994811

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
994811	2024-06-08 06:35:16	ducksaysquack	건포도 (IOI09_raisins)	C++98	100 / 100	865 ms	78820 KiB

raisins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> v(55,vector<int>(55)), p(55,vector<int>(55));
vector<vector<vector<vector<int>>>> dp(55,vector<vector<vector<int>>>(55,vector<vector<int>>(55,vector<int>(55,1e9))));
int f(int a, int b, int c, int d) {
  if(dp[a][b][c][d] != 1e9) return dp[a][b][c][d];
  if(a==c&&b==d) dp[a][b][c][d] = v[a][b];
  for(int i=a;i<c;i++) dp[a][b][c][d] = min(p[c+1][d+1]-p[a][d+1]-p[c+1][b]+p[a][b]+f(a,b,i,d)+f(i+1,b,c,d),dp[a][b][c][d]);
  for(int i=b;i<d;i++) dp[a][b][c][d] = min(p[c+1][d+1]-p[a][d+1]-p[c+1][b]+p[a][b]+f(a,b,c,i)+f(a,i+1,c,d),dp[a][b][c][d]);
  return dp[a][b][c][d];
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
  for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> v[i][j];
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+v[i-1][j-1];}
    f(0,0,n-1,m-1);
  cout << dp[0][0][n-1][m-1]-p[n][m] << '\n';
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 100 / 100