oj.uz

답안 #197051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197051 2020-01-18T10:34:18 Z Vlatko Mobitel (COCI19_mobitel) C++14
0 / 130
 6000 ms 1460 KB 
#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

# 결과 실행 시간 메모리 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