Submission #197051

#	Time	Username	Problem	Language	Result	Execution time	Memory
197051		Vlatko	Mobitel (COCI19_mobitel)	C++14	0 / 130	6096 ms	1460 KiB

mobitel

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int mod = 1e9 + 7;

inline void add_self(int& x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}

const int M = 310;

int R, C, N, ans;
int grid[M][M];
int ways[M][M]; // # paths to (R, C)

void dfs(int r, int c, ll prod) {
	prod *= grid[r][c];
	if (prod >= N) {
		add_self(ans, ways[r][c]);
	} else {
		if (r < R) dfs(r+1, c, prod);
		if (c < C) dfs(r, c+1, prod);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> R >> C >> N;
	for (int r = 1; r <= R; ++r) {
		for (int c = 1; c <= C; ++c) {
			cin >> grid[r][c];
		}
	}
	for (int r = R; r >= 1; --r) {
		for (int c = C; c >= 1; --c) {
			ways[r][c] = (r == R && c == C);
			if (r < R) add_self(ways[r][c], ways[r+1][c]);
			if (c < C) add_self(ways[r][c], ways[r][c+1]);
		}
	}
	ans = 0;
	dfs(1, 1, 1);
	cout << ans << endl;
}

• Subtask 1: 0 / 130