Submission #522261

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
522261	2022-02-04T10:58:37 Z	new_acc	Raisins (IOI09_raisins)	C++14	100 / 100	140 ms	41672 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	716 KB	Output is correct
6	Correct	1 ms	1356 KB	Output is correct
7	Correct	1 ms	1596 KB	Output is correct
8	Correct	4 ms	5080 KB	Output is correct
9	Correct	5 ms	6976 KB	Output is correct
10	Correct	7 ms	8376 KB	Output is correct
11	Correct	6 ms	7244 KB	Output is correct
12	Correct	17 ms	14448 KB	Output is correct
13	Correct	23 ms	18492 KB	Output is correct
14	Correct	8 ms	8984 KB	Output is correct
15	Correct	28 ms	20500 KB	Output is correct
16	Correct	5 ms	6976 KB	Output is correct
17	Correct	14 ms	14172 KB	Output is correct
18	Correct	70 ms	31652 KB	Output is correct
19	Correct	117 ms	38860 KB	Output is correct
20	Correct	140 ms	41672 KB	Output is correct