Submission #798062

#	Time	Username	Problem	Language	Result	Execution time	Memory
798062		YassirSalama	Raisins (IOI09_raisins)	C++14	100 / 100	433 ms	71980 KiB

raisins

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#define dbg(x) cout << "[ " << #x << " ] : " << x<<endl;
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=55;
const int INF=1e18;
int arr[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
int solve(int a,int b,int c,int d){
	if(dp[a][b][c][d]!=-1) return dp[a][b][c][d];
 	int ans=INF;
 	int sq=0;
 	//square sum
 	for(int i=a;i<=c;i++){
 		for(int j=b;j<=d;j++) sq+=arr[i][j];
 	}
 	//vertical cuts
 	for(int i=a+1;i<=c;i++){
 		int left,right;
 		left=solve(a,b,i-1,d);
 		right=solve(i,b,c,d);
 		ans=min(ans,left+right+sq);
 	}
 	//horizontal cut
 	for(int i=b+1;i<=d;i++){
 		int top,bot;
 		top=solve(a,i,c,d);
 		bot=solve(a,b,c,i-1);
 		ans=min(ans,top+bot+sq);
 	}
 	return dp[a][b][c][d]=ans;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
int m;
cin>>m;
for(int i=0;i<n;i++){
	for(int j=0;j<m;j++) cin>>arr[i][j];
}
memset(dp,-1,sizeof(dp));
for(int i=0;i<MAXN;i++){
	for(int j=0;j<MAXN;j++){
		for(int k=0;k<MAXN;k++){
			for(int kk=0;kk<MAXN;kk++){
				if(i==k&&j==kk) dp[i][j][k][kk]=0;
			}
		}
	}
}
cout<<solve(0,0,n-1,m-1)<<endl;
}

• Subtask 1: 100 / 100