Submission #100677

#TimeUsernameProblemLanguageResultExecution timeMemory
100677pzdbaMobitel (COCI19_mobitel)C++14
26 / 130
2115 ms5596 KiB
#include <bits/stdc++.h> using namespace std; int mod = 1000000007; int a[305][305]; int dp[2][2][305][1005]; int add(int a, int b){ return (a+b)%mod; } int main(){ int r, c, n; scanf("%d%d%d", &r, &c, &n); for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) scanf("%d", &a[i][j]); if(n <= 1000){ int pv = 0, nt = 1; for(int i=2;i<=r+c;i++){ memset(dp[nt][0], 0, sizeof(dp[nt][0])); memset(dp[nt][1], 0, sizeof(dp[nt][1])); for(int y=1;y<=r;y++){ int x = i-y; if(y > r || x > c || y < 1 || x < 1) continue; if(i == 2){ if(a[y][x] >= n) dp[nt][0][y][n] = add(dp[nt][0][y][n], 1); else dp[nt][0][y][a[y][x]] = add(dp[nt][0][y][a[y][x]], 1); } else{ for(int j=1;j<=n;j++){ int k = j*a[y][x]; if(k >= n){ dp[nt][0][y][n] = add(dp[nt][0][y][n], dp[pv][0][y][j]); if(y-1 >= 1) dp[nt][0][y][n] = add(dp[nt][0][y][n], dp[pv][0][y-1][j]); } else{ dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y][j]); if(y-1 >= 1) dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y-1][j]); } } } } swap(pv, nt); } printf("%d\n", dp[pv][0][r][n]); } else{ int pv = 0, nt = 1; for(int i=2;i<=r+c;i++){ memset(dp[nt][0], 0, sizeof(dp[nt][0])); memset(dp[nt][1], 0, sizeof(dp[nt][1])); for(int y=1;y<=r;y++){ int x = i-y; if(y > r || x > c || y < 1 || x < 1) continue; if(i == 2){ if(a[y][x] >= n) dp[nt][1][y][1] = add(dp[nt][1][y][1], 1); else{ int k = a[y][x]; if(a[y][x] > 1000){ k = (n+k-1)/k; dp[nt][1][y][k] = add(dp[nt][1][y][k], 1); if(y-1 >= 1) dp[nt][1][y][k] = add(dp[nt][1][y][k], 1); } else{ dp[nt][0][y][k] = add(dp[nt][0][y][k], 1); if(y-1 >= 1) dp[nt][0][y][k] = add(dp[nt][0][y][k], 1); } } } else{ for(int j=1;j<=1000;j++){ int k = j*a[y][x]; if(k > 1000){ k = (n+k-1)/k; dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][0][y][j]); if(y-1 >= 1) dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][1][y-1][j]); } else{ dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y][j]); if(y-1 >= 1) dp[nt][0][y][k] = add(dp[nt][0][y][k], dp[pv][0][y-1][j]); } } for(int j=1;j<=1000;j++){ int k = (j+a[y][x]-1)/a[y][x]; dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][1][y][j]); if(y-1 >= 1) dp[nt][1][y][k] = add(dp[nt][1][y][k], dp[pv][1][y-1][j]); } } } swap(pv, nt); } printf("%d\n", dp[pv][1][r][1]); } }

Compilation message (stderr)

mobitel.cpp: In function 'int main()':
mobitel.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &r, &c, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:12:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) scanf("%d", &a[i][j]);
                                                 ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...