Submission #522261

#	Time	Username	Problem	Language	Result	Execution time	Memory
522261		new_acc	Raisins (IOI09_raisins)	C++14	100 / 100	140 ms	41672 KiB

raisins

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (int)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=51;
int dp[N][N][N][N],sum[N][N][N][N];
int t[N][N];
void solve(){
	int n,m;
	cin>>n>>m;
	rep(i,n) rep(j,m) cin>>t[i][j];
	for(int i=n-1;i>=0;i--) for(int j=m-1;j>=0;j--){
		for(int x=i;x<n;x++){
			for(int y=j;y<m;y++)
				sum[i][j][x][y]=(x>0 and y>0?sum[i][j][x-1][y-1]:0)+(x>0?sum[i][y][x-1][y]:0)+(y>0?sum[x][j][x][y-1]:0)+t[x][y];
		}
	}
	for(int i=n-1;i>=0;i--){
		for(int j=m-1;j>=0;j--){
			for(int x=i;x<n;x++){
				for(int y=j;y<m;y++){
					if(i==x and y==j) continue;
					dp[i][j][x][y]=INT_MAX;
					for(int k=j;k<y;k++) dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][j][x][k]+dp[i][k+1][x][y]);
					for(int k=i;k<x;k++) dp[i][j][x][y]=min(dp[i][j][x][y],dp[i][j][k][y]+dp[k+1][j][x][y]);
					dp[i][j][x][y]+=sum[i][j][x][y];
				}
			}
		}
	}
	cout<<dp[0][0][n-1][m-1]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

• Subtask 1: 100 / 100