oj.uz

Submission #774184

# Submission time Handle Problem Language Result Execution time Memory
774184 2023-07-05T12:45:27 Z shoryu386 Mobitel (COCI19_mobitel) C++17
0 / 130
 462 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX 307
#define MOD 1000000007
int r, c, n;
unordered_map<int, int> smolbrain[MAX][MAX];
int arr[MAX][MAX];

inline int submod(int reeee){
	if (reeee >= MOD) return reeee-MOD;
	else return reeee;
}


main(){
	cin >> r >> c >> n;
	
	for (int x = 0; x < r; x++){ for (int y = 0; y < c; y++) cin >> arr[x][y];}
	
	smolbrain[0][0][arr[0][0]] = 1;
	
	int cringe[MAX][MAX];
	for (int x = 0; x < r; x++) cringe[x][0] = 1;
	for (int x = 0; x < c; x++) cringe[0][x] = 1;
	for (int y = 1; y < r; y++){
		for (int x = 1; x < c; x++){
			cringe[y][x] = submod(cringe[y-1][x] + cringe[y][x-1]);
		}
	}
	
	for (int y = 0; y < r; y++){
		for (int x = 0; x < c; x++){
			if (y < r-1){
				for (auto i : smolbrain[y][x]){
					if ((long long)i.first * (long long)arr[y+1][x] < n) smolbrain[y+1][x][ i.first * arr[y+1][x] ] = submod(smolbrain[y+1][x][ i.first * arr[y+1][x] ] + i.second); 
				}
			}
			
			if (x < c-1){
				for (auto i : smolbrain[y][x]){
					if ((long long)i.first * (long long)arr[y][x+1] < n) smolbrain[y][x+1][ i.first * arr[y][x+1] ] = submod(smolbrain[y][x+1][ i.first * arr[y][x+1] ] + i.second); 
				}
			}
			
			if (y != r-1 || x != c-1) smolbrain[y][x].clear();
		}
	}
	
	/*
	for (int y = 0; y < r; y++){
		for (int x = 0; x < c; x++){
			cout << "DEBUG FOR " << y << ' ' << x << '\n';
			for (auto i : smolbrain[y][x]){
				cout << i.first << ' ' << i.second << '\n';
			}
		}
	}
	*/
	
	int presum = 0;
	for (auto i : smolbrain[r-1][c-1]){
		presum = submod(presum + i.second);
	}
	
	cout << (cringe[r-1][c-1] - presum + MOD)%MOD;
}

Compilation message

mobitel.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~

Subtask #1
0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 365 ms 65536 KB Execution killed with signal 9
2 Runtime error 462 ms 65536 KB Execution killed with signal 9
3 Runtime error 412 ms 65536 KB Execution killed with signal 9
4 Runtime error 440 ms 65536 KB Execution killed with signal 9
5 Runtime error 363 ms 65536 KB Execution killed with signal 9
6 Runtime error 362 ms 65536 KB Execution killed with signal 9
7 Runtime error 377 ms 65536 KB Execution killed with signal 9
8 Runtime error 265 ms 65536 KB Execution killed with signal 9
9 Runtime error 245 ms 65536 KB Execution killed with signal 9
10 Runtime error 216 ms 65536 KB Execution killed with signal 9