oj.uz

Submission #225224

# Submission time Handle Problem Language Result Execution time Memory
225224 2020-04-19T15:51:53 Z Vimmer Mobitel (COCI19_mobitel) C++14
0 / 130
 50 ms 13300 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 200005
#define MOD ll(1e9 + 7)

using namespace std;

typedef long long ll;


int dp[2][301][2005], opr[1000005];

ll a[301][301];

vector <ll> vr;

int oprr(int x) {return opr[x];}


int main()
{

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

    ll n, m, k;

    cin >> n >> m >> k;

    vr.pb(k);

    for (int i = 2; i <= k; i++)
    {
        ll val = vr.back() - 1;

        while ((val - 1) * i >= k) {opr[val] = sz(vr); val--;}

        opr[val] = sz(vr);

        if (vr.back() != val) vr.pb(val);
    }

    vr.pb(1e18);

    sort(vr.begin(), vr.end());

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

   dp[0][0][oprr(min(k, a[0][0]))] = 1;

    for (register int i = 0; i < n; i++)
        {
            for (register int j = 0; j < m; j++)
              for (register int u = 0; u < sz(vr) - 1; u++)
                {
                    if (dp[0][j][u] == 0) continue;

                    ll val = vr[u];

                    if (i + 1 != n) dp[1][j][oprr(min(k, val * a[i + 1][j]))] = (dp[1][j][oprr(min(k, val * a[i + 1][j]))] + dp[0][j][u]) % MOD;

                    if (j + 1 != m) dp[0][j + 1][oprr(min(k, val * a[i][j + 1]))] = (dp[0][j + 1][oprr(min(k, val * a[i][j + 1]))] + dp[0][j][u]) % MOD;
                }

            if (i + 1 != n)
            {
                for (register int j = 0; j < m; j++)
                  for (register int u = 0; u < sz(vr) - 1; u++) {dp[0][j][u] = dp[1][j][u]; dp[1][j][u] = 0;}
            }
        }

    cout << dp[0][m - 1][sz(vr) - 2];
}

Subtask #1
0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 8092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 50 ms 8156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 21 ms 12404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 17 ms 13300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 19 ms 13172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 20 ms 13172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 17 ms 12532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 17 ms 13172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 19 ms 13172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 17 ms 13172 KB Execution killed with signal 11 (could be triggered by violating memory limits)