oj.uz

Submission #112011

# Submission time Handle Problem Language Result Execution time Memory
112011 2019-05-17T05:26:58 Z fredbr Mobitel (COCI19_mobitel) C++17
13 / 130
 1557 ms 8312 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];
        }

        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";
}

Subtask #1
13.0 / 130.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 8028 KB Output isn't correct
2 Correct 86 ms 8036 KB Output is correct
3 Incorrect 54 ms 7680 KB Output isn't correct
4 Incorrect 58 ms 7680 KB Output isn't correct
5 Incorrect 220 ms 7928 KB Output isn't correct
6 Incorrect 174 ms 7800 KB Output isn't correct
7 Incorrect 119 ms 7764 KB Output isn't correct
8 Incorrect 871 ms 8228 KB Output isn't correct
9 Incorrect 1490 ms 8192 KB Output isn't correct
10 Incorrect 1557 ms 8312 KB Output isn't correct