oj.uz

Submission #1081721

# Submission time Handle Problem Language Result Execution time Memory
1081721 2024-08-30T09:34:10 Z peacebringer1667 Raisins (IOI09_raisins) C++17
100 / 100
 197 ms 37200 KB 
#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 55;

int a[maxn][maxn],pre[maxn][maxn];
void input(int n,int m){
	for (int i = 1 ; i <= n ; i++)
	  for (int j = 1 ; j <= m ; j++) cin >> a[i][j];
}

void prepare(int n,int m){
	for (int i = 1 ; i <= n ; i++)
	  for (int j = 1 ; j <= m ; j++)
	  	pre[i][j] = a[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
}
int sum(int x1,int y1,int x2,int y2){
	int ans = pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
	return ans;
}

ll dp[maxn][maxn][maxn][maxn];

void perform(int lx,int ly,int n,int m){
	if (lx == 1 && ly == 1) return;
	
	for (int x1 = 1 ; x1 <= n - lx + 1 ; x1++)
	  for (int y1 = 1 ; y1 <= m - ly + 1 ; y1++){
	  	int x2 = x1 + lx - 1,y2 = y1 + ly - 1;
	  	
	  	ll T = INT_MAX;
	  	
	  	for (int i = x1 ; i < x2 ; i++)
	  	  T = min(T,dp[x1][y1][i][y2] + dp[i + 1][y1][x2][y2]);
	  	
	  	for (int i = y1 ; i < y2 ; i++)
	  	  T = min(T,dp[x1][y1][x2][i] + dp[x1][i + 1][x2][y2]);
	  	  
	  	dp[x1][y1][x2][y2] = T + sum(x1,y1,x2,y2);
	  }
}

ll solve(int n,int m){
	for (int lx = 1 ; lx <= n ; lx++)
	  for (int ly = 1 ; ly <= m ; ly++)
	     perform(lx,ly,n,m);
	
	return dp[1][1][n][m];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int n,m;
	cin >> n >> m;
	input(n,m);
	prepare(n,m);
	
	cout << solve(n,m);
	
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 3 ms 3676 KB Output is correct
9 Correct 5 ms 5212 KB Output is correct
10 Correct 6 ms 6232 KB Output is correct
11 Correct 6 ms 5208 KB Output is correct
12 Correct 18 ms 11100 KB Output is correct
13 Correct 28 ms 14388 KB Output is correct
14 Correct 9 ms 6492 KB Output is correct
15 Correct 36 ms 16212 KB Output is correct
16 Correct 4 ms 5972 KB Output is correct
17 Correct 16 ms 11816 KB Output is correct
18 Correct 84 ms 27352 KB Output is correct
19 Correct 140 ms 34032 KB Output is correct
20 Correct 197 ms 37200 KB Output is correct