oj.uz

Submission #798062

# Submission time Handle Problem Language Result Execution time Memory
798062 2023-07-30T10:37:23 Z YassirSalama Raisins (IOI09_raisins) C++14
100 / 100
 433 ms 71980 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 71884 KB Output is correct
2 Correct 35 ms 71932 KB Output is correct
3 Correct 33 ms 71940 KB Output is correct
4 Correct 35 ms 71848 KB Output is correct
5 Correct 34 ms 71892 KB Output is correct
6 Correct 34 ms 71892 KB Output is correct
7 Correct 35 ms 71932 KB Output is correct
8 Correct 38 ms 71920 KB Output is correct
9 Correct 41 ms 71892 KB Output is correct
10 Correct 44 ms 71956 KB Output is correct
11 Correct 42 ms 71832 KB Output is correct
12 Correct 63 ms 71960 KB Output is correct
13 Correct 85 ms 71892 KB Output is correct
14 Correct 47 ms 71844 KB Output is correct
15 Correct 97 ms 71952 KB Output is correct
16 Correct 40 ms 71940 KB Output is correct
17 Correct 57 ms 71888 KB Output is correct
18 Correct 204 ms 71912 KB Output is correct
19 Correct 347 ms 71980 KB Output is correct
20 Correct 433 ms 71956 KB Output is correct