Submission #197051

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
197051	2020-01-18T10:34:18 Z	Vlatko	Mobitel (COCI19_mobitel)	C++14	0 / 130	6000 ms	1460 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	6070 ms	1272 KB	Time limit exceeded
2	Execution timed out	6073 ms	1460 KB	Time limit exceeded
3	Execution timed out	6083 ms	632 KB	Time limit exceeded
4	Execution timed out	6087 ms	632 KB	Time limit exceeded
5	Execution timed out	6049 ms	632 KB	Time limit exceeded
6	Execution timed out	6085 ms	632 KB	Time limit exceeded
7	Execution timed out	6064 ms	504 KB	Time limit exceeded
8	Execution timed out	6096 ms	1016 KB	Time limit exceeded
9	Execution timed out	6019 ms	1272 KB	Time limit exceeded
10	Execution timed out	6046 ms	1272 KB	Time limit exceeded