oj.uz

Submission #405612

# Submission time Handle Problem Language Result Execution time Memory
405612 2021-05-16T15:11:32 Z Jasiekstrz Raisins (IOI09_raisins) C++17
100 / 100
 181 ms 18372 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF=1e9+7;
const int N=50;
int tab[N+10][N+10];
int pref[N+10][N+10];
int dp[N+10][N+10][N+10][N+10];
int sum(int li,int ri,int lj,int rj)
{
	return pref[ri][rj]-pref[ri][lj-1]-pref[li-1][rj]+pref[li-1][lj-1];
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>tab[i][j];
			pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+tab[i][j];
		}
	}
	for(int di=0;di<=n;di++)
	{
		for(int dj=(di==0 ? 1:0);dj<=m;dj++)
		{
			for(int li=1,ri=di+1;ri<=n;li++,ri++)
			{
				for(int lj=1,rj=dj+1;rj<=m;lj++,rj++)
				{
					dp[li][ri][lj][rj]=INF;
					for(int k=li;k<ri;k++)
						dp[li][ri][lj][rj]=min(dp[li][ri][lj][rj],
								dp[li][k][lj][rj]+dp[k+1][ri][lj][rj]);
					for(int k=lj;k<rj;k++)
						dp[li][ri][lj][rj]=min(dp[li][ri][lj][rj],
								dp[li][ri][lj][k]+dp[li][ri][k+1][rj]);
					dp[li][ri][lj][rj]+=sum(li,ri,lj,rj);
				}
			}
		}
	}
	cout<<dp[1][n][1][m]<<"\n";
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 964 KB Output is correct
8 Correct 3 ms 1852 KB Output is correct
9 Correct 4 ms 3008 KB Output is correct
10 Correct 5 ms 3532 KB Output is correct
11 Correct 4 ms 2624 KB Output is correct
12 Correct 15 ms 6240 KB Output is correct
13 Correct 25 ms 7952 KB Output is correct
14 Correct 6 ms 3044 KB Output is correct
15 Correct 32 ms 8972 KB Output is correct
16 Correct 6 ms 5324 KB Output is correct
17 Correct 16 ms 8268 KB Output is correct
18 Correct 120 ms 15688 KB Output is correct
19 Correct 163 ms 17016 KB Output is correct
20 Correct 181 ms 18372 KB Output is correct