Submission #1081721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081721		peacebringer1667	Raisins (IOI09_raisins)	C++17	100 / 100	197 ms	37200 KiB

raisins

#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 / 100