# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
112011 | fredbr | Mobitel (COCI19_mobitel) | C++17 | 1557 ms | 8312 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int const maxk = 3000;
int const maxd = 301;
int const maxn = 1010101;
int const mod = 1e9 + 7;
int atual = 0;
int cor[maxk], cr[maxn];
inline int get_rv(int x) {
if (cr[x] == 0) {
cor[++atual] = x;
cr[x] = atual;
}
return cr[x];
}
inline int iceil(int x, int y) {
return x/y + (x%y ==0? 0 : 1);
}
int v[maxd][maxd];
int dp[2][maxd][maxk];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> v[i][j];
int now = 1, old = 0;
dp[now][m][get_rv(k)] = 1;
for (int i = n; i >= 1; i--) {
swap(now, old);
memset(dp[now], 0, sizeof(dp[now]));
for (int p = 1; p <= atual; p++) {
dp[now][m][get_rv(iceil(cor[p], v[i][m]))] += dp[old][m][p];
}
for (int j = m-1; j >= 1; j--) {
for (int p = 1; p <= atual; p++) {
int c = cor[p];
dp[now][j][get_rv(iceil(c, v[i][j]))] += dp[now][j+1][p];
if (i != n) {
dp[now][j][get_rv(iceil(c, v[i][j]))] += dp[old][j][p];
dp[now][j][get_rv(iceil(c, v[i][j]))] %= mod;
}
}
}
// cout << "linha " << i << "\n";
// for (int p = 1; p <= atual; p++) {
// cout << "cor : " << cor[p] << " (" << p << ")" << "\n";
// for (int j = 1; j <= m; j++)
// cout << dp[now][j][p] <<' ';
// cout << "\n";
// }
// cout << "\n";
}
cout << dp[now][1][get_rv(1)] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |