oj.uz

Submission #225173

# Submission time Handle Problem Language Result Execution time Memory
225173 2020-04-19T10:54:09 Z Vimmer Mobitel (COCI19_mobitel) C++14
0 / 130
 123 ms 65540 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define MOD ll(1e9 + 7)

using namespace std;

typedef long long ll;

typedef long double ld;



ll a[105][105], dp[105][105], f[105][105][105][105], n, m, s, ans;

int mk[105][105];

vector <pair <ll, ll> >  vr;


void rec(int x, int y, ll sm, ll kol);

void dfs(int x, int y, int xr, int yr, int id)
{
    if (mk[x][y] == id) return;

    mk[x][y] = id;

    if (x + 1 != n)
    {
        if (a[x + 1][y] == 1) dfs(x + 1, y, xr, yr, id);
          else rec(x + 1, y, vr[id - 1].F * a[x + 1][y], (vr[id - 1].S * f[x][y][xr][yr]) % MOD);
    }

    if (y + 1 != m)
    {
        if (a[x][y + 1] == 1) dfs(x, y + 1, xr, yr, id);
          else rec(x, y + 1, vr[id - 1].F * a[x][y + 1], (vr[id - 1].S * f[x][y][xr][yr]) % MOD);
    }
}

void rec(int x, int y, ll sm, ll kol)
{
    if (sm >= s) {ans = (ans + (kol * dp[x][y]) % MOD) % MOD; return;}

    if (a[x][y] == 1) {vr.pb({sm, kol}); dfs(x, y, x, y, sz(vr)); return;}

    if (x + 1 != n) rec(x + 1, y, sm * a[x + 1][y], kol);

    if (y + 1 != m) rec(x, y + 1, sm * a[x][y + 1], kol);
}


int main()
{

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> s;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> a[i][j];

    dp[n - 1][m - 1] = 1;

    for (int i = n - 1; i >= 0; i--)
        for (int j = m - 1; j >= 0; j--)
        {
            if (i + 1 != n) dp[i][j] = (dp[i][j] + dp[i + 1][j]) % MOD;

            if (j + 1 != m) dp[i][j] = (dp[i][j] + dp[i][j + 1]) % MOD;
        }

    for (int xr = 0; xr < n; xr++)
        for (int yr = 0; yr < m; yr++)
        {
            if (a[xr][yr] != 1) continue;

            for (int x = 0; x < n; x++)
                for (int y = 0; y < m; y++) f[x][y][xr][yr] = 0;

            f[xr][yr][xr][yr] = 1;

            for (int x = 0; x < n; x++)
                for (int y = 0; y < m; y++)
                {
                    if (x != 0 && a[x - 1][y] == 1) f[x][y][xr][yr] = (f[x][y][xr][yr] + f[x - 1][y][xr][yr]) % MOD;

                    if (y != 0 && a[x][y - 1] == 1) f[x][y][xr][yr] = (f[x][y][xr][yr] + f[x][y - 1][xr][yr]) % MOD;
                }
        }
    rec(0, 0, a[0][0], 1);

    cout << ans << endl;
}

Subtask #1
0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 46 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 112 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 106 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 107 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 109 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 123 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 42 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 45 ms 432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 47 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)