| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 100679 |
2019-03-13T07:24:26 Z |
pzdba |
Mobitel (COCI19_mobitel) |
C++14 |
|
2111 ms |
5624 KB |
#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][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]);
}
}
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
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 time |
Memory |
Grader output |
| 1 |
Correct |
422 ms |
5624 KB |
Output is correct |
| 2 |
Correct |
354 ms |
5504 KB |
Output is correct |
| 3 |
Correct |
235 ms |
5248 KB |
Output is correct |
| 4 |
Correct |
267 ms |
5248 KB |
Output is correct |
| 5 |
Correct |
283 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
265 ms |
5368 KB |
Output is correct |
| 7 |
Correct |
149 ms |
5248 KB |
Output is correct |
| 8 |
Correct |
1154 ms |
5504 KB |
Output is correct |
| 9 |
Correct |
2111 ms |
5504 KB |
Output is correct |
| 10 |
Correct |
1944 ms |
5624 KB |
Output is correct |
