oj.uz

Submission #105862

# Submission time Handle Problem Language Result Execution time Memory
105862 2019-04-15T11:12:06 Z hyn0027 Mobitel (COCI19_mobitel) C++11
130 / 130
 2508 ms 28772 KB 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
const int mod = 1e9 + 7, maxn = 302, maxmmax = 1e6 + 10;
int n, m, mmax, s[maxn][maxn], f[2][maxn][3010], bel[maxmmax], c, mp[maxmmax], premp[maxmmax], ans;
signed main(){
//	freopen("mobitel.in", "r", stdin);
//	freopen("mobitel.out", "w", stdout);
	scanf("%lld%lld%lld", &n, &m, &mmax);
	bel[0] = mmax + 1;
	for(int i = 1; i <= mmax; i++){
		bel[i] = bel[i - 1];
		while(bel[i] * i >= mmax)	bel[i]--;
		bel[i]++;
		if(bel[i] != bel[i - 1]) c++;
		mp[c] = i;
		premp[i] = c;
	}
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%lld", &s[i][j]);
	f[0][0][premp[1]] = 1;
	for(int ii = 0, i = 0; ii < n; ii++, i ^= 1)
		for(int j = 0; j < m; j++)
			for(int k = 1, cur; k <= c; k++){
				cur = min(mmax, mp[k] * s[ii][j]);
				if(cur == mmax && ii == n - 1 && j == m - 1 && f[i][j][k])	ans += f[i][j][k];
				f[i][j + 1][premp[cur]] += f[i][j][k], f[i][j + 1][premp[cur]] %= mod;
				f[!i][j][premp[cur]] += f[i][j][k], f[!i][j][premp[cur]] %= mod;
				f[i][j][k] = 0;
			}
	ans %= mod;
	printf("%lld\n", ans);
	return 0;
}

Compilation message

mobitel.cpp: In function 'int main()':
mobitel.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &m, &mmax);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &s[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3840 KB Output is correct
2 Correct 41 ms 3960 KB Output is correct
3 Correct 143 ms 18404 KB Output is correct
4 Correct 140 ms 20216 KB Output is correct
5 Correct 305 ms 20388 KB Output is correct
6 Correct 249 ms 20216 KB Output is correct
7 Correct 149 ms 17656 KB Output is correct
8 Correct 1260 ms 25244 KB Output is correct
9 Correct 2508 ms 28408 KB Output is correct
10 Correct 2497 ms 28772 KB Output is correct