Submission #112012

#	Time	Username	Problem	Language	Result	Execution time	Memory
112012		fredbr	Mobitel (COCI19_mobitel)	C++17	130 / 130	2564 ms	8184 KiB

mobitel

#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];
            dp[now][m][get_rv(iceil(cor[p], v[i][m]))] %= mod;
        }

        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];

                dp[now][j][get_rv(iceil(c, v[i][j]))] %= mod;
                
                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";
}

• Subtask 1: 130 / 130