oj.uz

Submission #112012

# Submission time Handle Problem Language Result Execution time Memory
112012 2019-05-17T05:28:29 Z fredbr Mobitel (COCI19_mobitel) C++17
130 / 130
 2564 ms 8184 KB 
#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.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7808 KB Output is correct
2 Correct 96 ms 7824 KB Output is correct
3 Correct 70 ms 7808 KB Output is correct
4 Correct 84 ms 7808 KB Output is correct
5 Correct 245 ms 7808 KB Output is correct
6 Correct 192 ms 7780 KB Output is correct
7 Correct 118 ms 7680 KB Output is correct
8 Correct 1096 ms 8056 KB Output is correct
9 Correct 2122 ms 8184 KB Output is correct
10 Correct 2564 ms 8172 KB Output is correct