oj.uz

Submission #225042

# Submission time Handle Problem Language Result Execution time Memory
225042 2020-04-19T08:23:33 Z VEGAnn Mobitel (COCI19_mobitel) C++14
13 / 130
 280 ms 65540 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 = 110;
const int md = int(1e9) + 7;
const int SQ = 1010;
int f[N][N][SQ], ff[N][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[1][1][n / sq] = 1;
    else f[1][1][a[1][1]] = 1;

    for (int i = 1; i <= r; i++)
    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[i + 1][j][nw], f[i][j][k]);
                else SUM(ff[i + 1][j][n / nw], f[i][j][k]);
            }
            if (j + 1 <= c){
                int nw = k * a[i][j + 1];

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

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

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

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

    cout << ff[r][c][0];

    return 0;
}

Subtask #1
13.0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 15 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 261 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 278 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 280 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 276 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 164 ms 39800 KB Output is correct
8 Runtime error 15 ms 2688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 16 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 16 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)