oj.uz

Submission #225177

# Submission time Handle Problem Language Result Execution time Memory
225177 2020-04-19T11:00:18 Z Vimmer Mobitel (COCI19_mobitel) C++14
0 / 130
 187 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;



int a[101][101], dp[101][101], f[101][101][101][101], n, m, mk[101][101];

ll ans, s;

vector <pair <int, int> >  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, ll(ll(vr[id - 1].F) * ll(a[x + 1][y])), ll(ll(vr[id - 1].S) * ll(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, ll(ll(vr[id - 1].F) * ll(a[x][y + 1])), ll(ll(vr[id - 1].S) * ll(f[x][y][xr][yr])) % MOD);
    }
}

inline void rec(int x, int y, ll sm, ll kol)
{
    if (sm >= s) {ans = (ans + (kol * ll(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 * ll(a[x + 1][y]), kol);

    if (y + 1 != m) rec(x, y + 1, sm * ll(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 23 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 22 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 166 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 154 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 150 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 157 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 187 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 24 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 23 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 24 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)