Submission #309873

#	Time	Username	Problem	Language	Result	Execution time	Memory
309873		sofapuden	Raisins (IOI09_raisins)	C++14	75 / 100	1505 ms	89464 KiB

raisins

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> gra;
vector<vector<vector<vector<int>>>> dp(55, vector<vector<vector<int>>>(55, vector<vector<int>> (55, vector<int>(55, 0))));

int find(int x, int xb, int y, int yb){
	if(x == xb-1 && y == yb-1)return 0;
	if(dp[x][xb][y][yb])return dp[x][xb][y][yb];
	int r = INT_MAX;
	for(int i = x+1; i < xb; ++i){
		r = min(r,find(x,i,y,yb)+find(i,xb,y,yb));
	}
	for(int i = y+1; i < yb; ++i){
		r = min(r,find(x,xb,y,i)+find(x,xb,i,yb));
	}
	dp[x][xb][y][yb] = r+gra[xb][yb]+gra[x][y]-gra[xb][y]-gra[x][yb];
	return dp[x][xb][y][yb];
}

int main(){
	int n, m; cin >> n >> m;
	gra.resize(n+1, vector<int>(m));
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			cin >> gra[i][j];
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			gra[i][j]+=gra[i-1][j]+gra[i][j-1]-gra[i-1][j-1];
		}
	}
	cout << find(0,n,0,m) << "\n";
}
	
	

• Subtask 1: 75 / 100