oj.uz

Submission #225046

# Submission time Handle Problem Language Result Execution time Memory
225046 2020-04-19T08:28:17 Z VEGAnn Mobitel (COCI19_mobitel) C++14
0 / 130
 3088 ms 5624 KB 
#include <bits/stdc++.h>
#define MP make_pair
#define PB push_back
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int N = 310;
const int md = int(1e9) + 7;
const int SQ = 1010;
int f[2][N][SQ], ff[2][N][SQ], r, c, n, a[N][N], sq, osq, kol[N][N];

void SUM(int &x, int y){
    x += y;
    if (x >= md)
        x -= md;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> r >> c >> n;

    n--;

    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            cin >> a[i][j];

    sq = (int)trunc(sqrt(n));
    osq = n / (sq + 1);

    if (a[1][1] > sq)
        ff[0][1][n / sq] = 1;
    else f[0][1][a[1][1]] = 1;

    int it = 0;

    // NULL EVERYTHING!!!

    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++){
            for (int k = 1; k <= sq; k++)
                f[it ^ 1][j][k] = 0;
            for (int ok = 0; ok <= osq; ok++)
                ff[it ^ 1][j][ok] = 0;
        }

        for (int j = 1; j <= c; j++) {
            for (int k = 1; k <= sq; k++){
                if (i + 1 <= r){
                    int nw = k * a[i + 1][j];

                    if (nw <= sq)
                        SUM(f[it ^ 1][j][nw], f[it][j][k]);
                    else SUM(ff[it ^ 1][j][n / nw], f[it][j][k]);
                }
                if (j + 1 <= c){
                    int nw = k * a[i][j + 1];

                    if (nw <= sq)
                        SUM(f[it][j + 1][nw], f[it][j][k]);
                    else SUM(ff[it][j + 1][n / nw], f[it][j][k]);
                }
            }

            for (int ok = 0; ok <= osq; ok++){
                if (i + 1 <= r){
                    int nw = ok / a[i + 1][j];

                    SUM(ff[it ^ 1][j][nw], ff[it][j][ok]);
                }
                if (j + 1 <= c){
                    int nw = ok / a[i][j + 1];

                    SUM(ff[it ^ 1][j + 1][nw], ff[it][j][ok]);
                }
            }
        }

        it ^= 1;
    }

    cout << ff[it ^ 1][c][0];

    return 0;
}

Subtask #1
0 / 130.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 5376 KB Output isn't correct
2 Incorrect 62 ms 5504 KB Output isn't correct
3 Incorrect 308 ms 2048 KB Output isn't correct
4 Incorrect 345 ms 2048 KB Output isn't correct
5 Incorrect 332 ms 2144 KB Output isn't correct
6 Incorrect 344 ms 2048 KB Output isn't correct
7 Incorrect 159 ms 1656 KB Output isn't correct
8 Incorrect 1651 ms 4096 KB Output isn't correct
9 Incorrect 3066 ms 5496 KB Output isn't correct
10 Incorrect 3088 ms 5624 KB Output isn't correct