Submission #1346165

#TimeUsernameProblemLanguageResultExecution timeMemory
1346165po_rag526Mobitel (COCI19_mobitel)C++17
0 / 130
634 ms5872 KiB
#include <iostream>

using namespace std;
const int N = 301;
int a[2 * N][2 * N];
int dp[2][2][2 * N][1005];

int get(int x, int y){
	if (y == 0)
		y++;
	return (x / y) + (x % y > 0);
}

int main(){
	int n, m, K;
	cin>>n>>m>>K;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++)
			cin>>a[i][j];
	}

	if (a[1][1] < get(K, a[1][1]))
		dp[0][0][1][a[1][1]] = 1;
	else
		dp[0][1][1][get(K, a[1][1])] = 1;

	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			for (int k=1;k<=1000;k++){
				{
					int A = k * a[i][j+1], B = get(K, A);

					if (A < B)
						dp[0][0][j+1][A] += dp[0][0][j][k];
					else
						dp[0][1][j+1][B] += dp[0][0][j][k];

					A = get(k, a[i][j+1]);
					dp[0][1][j+1][A] += dp[0][1][j][k];
				}

				{
					int A = k * a[i+1][j], B = get(K, A);

					if (A < B)
						dp[1][0][j][A] += dp[0][0][j][k];
					else
						dp[1][1][j][B] += dp[0][0][j][k];

					A = get(k, a[i+1][j]);
					dp[1][1][j][A] += dp[0][1][j][k];
				}
			}
		}
		for (int j=1;j<=m;j++){
			for (int k=1;k<=1000;k++){
				// if (dp[1][0][j][k] + dp[1][1][j][k])
				// 	cout<<i<<' '<<j<<' '<<k<<" :: "<<dp[1][0][j][k]<<' '<<dp[1][1][j][k]<<endl;
				for (int t : {0, 1})
					dp[0][t][j][k] = dp[1][t][j][k], dp[1][t][j][k] = 0;
			}
		}
	}

	cout<<dp[0][1][m][1]<<'\n';


}
#Verdict Execution timeMemoryGrader output
Fetching results...