oj.uz

Submission #225099

# Submission time Handle Problem Language Result Execution time Memory
225099 2020-04-19T09:24:09 Z kartel Mobitel (COCI19_mobitel) C++14
65 / 130
 133 ms 12160 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define F first
#define S second
#define pb push_back
#define M ll(1e9 + 7)
#define inf ll(2e9+7)
#define N ll(305)
#define sz(x) x.size()
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
#define el '\n'
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> os;

ll n, m, x, i, j, f[2][N][1050][2], a[N][N], k, sq, ans, fc[N];

ll sm(ll x, ll y) {return (0ll + x + y) % M;}

ll pw(ll x, ll y)
{
    if (y == 0) return 1ll;
    if (y % 2) return pw(x, y - 1) * x % M;
    ll a = pw(x, y / 2ll);
    return a * a % M;
}

ll C(ll n, ll k)
{
    return (fc[n] * pw((fc[n - k] * fc[k]) % M, M - 2)) % M;
}

int main()
{
//    in("input.txt");
//    out("output.txt");

    ios_base::sync_with_stdio(false);
    iostream::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> x;
    x--;

    sq = int(sqrt(x));

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

    fc[1] = 1;
    for (i = 2; i <= n + m; i++) fc[i] = (fc[i - 1] * i) % M;

    ans = C(n + m - 2, n - 1);

    if (sq == 1) f[0][1][0][1] = 1;
            else f[0][1][1][0] = 1;

    for (i = 1; i <= n; i++)
      {
         for (j = 1; j <= m; j++)
            for (k = 1; k <= max(x / sq, sq); k++) f[i % 2][j][k][0] = f[i % 2][j][k][1] = 0;
         for (j = 1; j <= m; j++)
            for (k = 1; k <= max(x / sq, sq); k++)
         {
             ll nk = k * a[i][j];
             if (nk < sq)
             {
                 f[i % 2][j][nk][0] = sm(f[i % 2][j][nk][0], f[(i + 1) % 2][j][k][0]);
                 f[i % 2][j][nk][0] = sm(f[i % 2][j][nk][0], f[i % 2][j - 1][k][0]);
             }
             else
             {
                 f[i % 2][j][x / nk][1] = sm(f[i % 2][j][x / nk][1], f[(i + 1) % 2][j][k][0]);
                 f[i % 2][j][x / nk][1] = sm(f[i % 2][j][x / nk][1], f[i % 2][j - 1][k][0]);
             }
             nk = k / a[i][j];
             f[i % 2][j][nk][1] = sm(f[i % 2][j][nk][1], f[(i + 1) % 2][j][k][1]);
             f[i % 2][j][nk][1] = sm(f[i % 2][j][nk][1], f[i % 2][j - 1][k][1]);
         }
      }
    for (i = 1; i <= max(x / sq, sq); i++)
    {
        ans = sm(ans, M - f[n % 2][m][i][1]);
        ans = sm(ans, M - f[n % 2][m][i][0]);
    }
    cout << ans;
}

Subtask #1
65.0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 20 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 121 ms 3840 KB Output is correct
4 Correct 128 ms 3840 KB Output is correct
5 Correct 131 ms 3840 KB Output is correct
6 Correct 133 ms 3840 KB Output is correct
7 Correct 66 ms 2816 KB Output is correct
8 Runtime error 18 ms 11648 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 20 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 20 ms 12032 KB Execution killed with signal 11 (could be triggered by violating memory limits)