#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define pw(x) (1<<(x))
#define inf 100000009
#define MOD 1000000007
#define N 305
#define M 2500005
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;
int n,m,val;
int a[N][N];
int dp[2][N][1005][2];
int w[2][2]={1,0,0,1};
int add(int x,int y) {
x+=y;
if(x>=MOD) x-=MOD;
if(x<0) x+=MOD;
return x;
}
int main() {
scanf("%d %d %d",&n,&m,&val);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
if(a[1][1]<=1000) {
dp[1][1][a[1][1]][0]=1;
}
else {
dp[1][1][(val+a[1][1]-1)/a[1][1]][1]=1;
}
for(int i=1;i<=n;i++) {
int cur=i&1;
for(int j=1;j<=m;j++) {
for(int way=0;way<2;way++) {
int x=i+w[way][0];
int y=j+w[way][1];
if(x>n || y>m) continue ;
int gval=a[x][y];
for(int v=1;v<=1000;v++) {
int nv=v*gval;
if(nv<=1000) {
dp[cur^(x!=i)][y][nv][0]=add(dp[cur^(x!=i)][y][nv][0],dp[cur][j][v][0]);
}
else {
dp[cur^(x!=i)][y][(val+nv-1)/nv][1]=add(dp[cur^(x!=i)][y][(val+nv-1)/nv][1],dp[cur][j][v][0]);
}
dp[cur^(x!=i)][y][(v+gval-1)/gval][1]=add(dp[cur^(x!=i)][y][(v+gval-1)/gval][1],dp[cur][j][v][1]);
}
}
}
if(i!=n) {
for(int j=1;j<=m;j++) {
for(int v=1;v<=1000;v++) {
for(int w=0;w<2;w++) {
dp[cur][j][v][w]=0;
}
}
}
}
}
int ans=0;
for(int v=1;v<=1000;v++) {
if(v>=val) {
ans=add(ans,dp[n&1][m][v][0]);
}
}
ans=add(ans,dp[n&1][m][1][1]);
printf("%d",ans);
}
Compilation message
mobitel.cpp: In function 'int main()':
mobitel.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&n,&m,&val);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1715 ms |
5652 KB |
Output is correct |
| 2 |
Correct |
1806 ms |
5672 KB |
Output is correct |
| 3 |
Correct |
170 ms |
2088 KB |
Output is correct |
| 4 |
Correct |
173 ms |
2048 KB |
Output is correct |
| 5 |
Correct |
217 ms |
2048 KB |
Output is correct |
| 6 |
Correct |
221 ms |
2168 KB |
Output is correct |
| 7 |
Correct |
109 ms |
1656 KB |
Output is correct |
| 8 |
Correct |
1160 ms |
4184 KB |
Output is correct |
| 9 |
Correct |
2324 ms |
5632 KB |
Output is correct |
| 10 |
Correct |
2333 ms |
5648 KB |
Output is correct |
