Submission #1188237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188237		thinknoexit	Mobitel (COCI19_mobitel)	C++20	91 / 130	735 ms	6308 KiB

mobitel

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
ll a[303][303];
int dp[2][303][1010]; // end (i, j) such that mul == k
int dp2[2][303][1010]; // end (i, j) such that mul == n / k
int dp3[303][303];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    ll s;
    cin >> n >> m >> s;
    ll sq = sqrt(s);
    dp3[1][1] = 1;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
            dp3[i][j] = (dp3[i][j] + dp3[i - 1][j]) % MOD;
            dp3[i][j] = (dp3[i][j] + dp3[i][j - 1]) % MOD;
        }
    }
    if (s == 1) {
        cout << dp3[n][m] << '\n';
        return 0;
    }
    if (a[1][1] <= sq) dp[1][1][a[1][1]] = 1;
    else dp2[1][1][(s + a[1][1] - 1) / a[1][1]] = 1;
    for (int i = 1;i <= n;i++) {
        int now = i & 1, nxt = 1 - now;
        memset(dp[nxt], 0, sizeof dp[nxt]);
        memset(dp2[nxt], 0, sizeof dp2[nxt]);
        for (int j = 1;j <= m;j++) {
            for (int k = 1;k <= sq;k++) {
                // dp[i][j], dp2[i][j] -> dp[i+1][j], dp2[i+1][j]
                if (i != n) {
                    ll v = a[i + 1][j] * k;
                    if (v <= sq)
                        dp[nxt][j][v] = (dp[nxt][j][v] + dp[now][j][k]) % MOD;
                    else if (v < s)
                        v = (s + v - 1) / v,
                        dp2[nxt][j][v] = (dp2[nxt][j][v] + dp[now][j][k]) % MOD;
                    v = (k + a[i + 1][j] - 1) / a[i + 1][j];
                    if (v > 1)
                        dp2[nxt][j][v] = (dp2[nxt][j][v] + dp2[now][j][k]) % MOD;
                }
                // dp[i][j], dp2[i][j] -> dp[i][j+1], dp2[i][j+1]
                if (j != m) {
                    ll v = a[i][j + 1] * k;
                    if (v <= sq)
                        dp[now][j + 1][v] = (dp[now][j + 1][v] + dp[now][j][k]) % MOD;
                    else if (v < s)
                        v = (s + v - 1) / v,
                        dp2[now][j + 1][v] = (dp2[now][j + 1][v] + dp[now][j][k]) % MOD;
                    v = (k + a[i][j + 1] - 1) / a[i][j + 1];
                    if (v > 1)
                        dp2[now][j + 1][v] = (dp2[now][j + 1][v] + dp2[now][j][k]) % MOD;
                }
            }
        }
    }
    int ans = dp3[n][m];
    for (int i = 1;i <= sq;i++) {
        ans = (ans - dp[n & 1][m][i] + MOD) % MOD;
    }
    for (int i = 2;i <= sq;i++) {
        ans = (ans - dp2[n & 1][m][i] + MOD) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 91 / 130