Submission #877

2022-01-24 17:35:28

cpp11

Accepted 50/50

8ms

3900 KiB

#include <bits/stdc++.h>
#define MN 110
using namespace std;
//17:28
int dp[MN][MN][MN],t[MN][MN],n,m,kk;
signed main()
{
	cin>>n>>m>>kk;
	for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=kk;k++) dp[i][j][k]=INT_MAX;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>t[i][j];
	for(int k=0;k<=kk;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				int x=t[i][j];
				for(int l=0;l<=k;l++)
				{
					if(i==1 && j==1)dp[i][j][k]=x;
					else dp[i][j][k]=min(dp[i][j][k],min(dp[i-1][j][k-l],dp[i][j-1][k-l])+x);
					x>>=1;
				}
			}
		}
	}
	cout<<dp[n][m][kk]<<'\n';
	return 0;
}

	Sum	Test	Verdict		Time	Memory
base	50/50
		1	Accepted	0/0	1ms	1876 KiB
		2	Accepted	0/0	7ms	3636 KiB
		3	Accepted	2/2	2ms	3704 KiB
		4	Accepted	2/2	2ms	3720 KiB
		5	Accepted	3/3	2ms	3728 KiB
		6	Accepted	3/3	2ms	3748 KiB
		7	Accepted	2/2	6ms	3764 KiB
		8	Accepted	3/3	7ms	3776 KiB
		9	Accepted	2/2	8ms	2100 KiB
		10	Accepted	2/2	1ms	2112 KiB
		11	Accepted	3/3	1ms	2116 KiB
		12	Accepted	3/3	2ms	2116 KiB
		13	Accepted	2/2	3ms	2552 KiB
		14	Accepted	3/3	2ms	2556 KiB
		15	Accepted	2/2	7ms	3820 KiB
		16	Accepted	3/3	6ms	3828 KiB
		17	Accepted	2/2	7ms	3844 KiB
		18	Accepted	3/3	7ms	3852 KiB
		19	Accepted	2/2	7ms	3868 KiB
		20	Accepted	3/3	7ms	3880 KiB
		21	Accepted	2/2	7ms	3888 KiB
		22	Accepted	3/3	7ms	3900 KiB