oj.uz

Submission #225174

# Submission time Handle Problem Language Result Execution time Memory
225174 2020-04-19T10:56:08 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[101][101], dp[101][101], f[101][101][101][101], n, m, s, ans;

int mk[101][101];

vector <pair <ll, ll> >  vr;


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

inline 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);
    }
}

inline 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 40 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 38 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 113 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 109 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 108 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 117 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 123 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 39 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 39 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 41 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)