oj.uz

Submission #225089

# Submission time Handle Problem Language Result Execution time Memory
225089 2020-04-19T09:20:57 Z kartel Mobitel (COCI19_mobitel) C++14
0 / 130
 141 ms 6272 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;

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

int sm(int x, int 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;
}

int 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][1][1] = 1;
            else f[0][1][0][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
0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 6272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 15 ms 6272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 139 ms 2296 KB Output isn't correct
4 Incorrect 134 ms 2168 KB Output isn't correct
5 Incorrect 141 ms 2168 KB Output isn't correct
6 Incorrect 136 ms 2168 KB Output isn't correct
7 Incorrect 67 ms 1664 KB Output isn't correct
8 Runtime error 12 ms 6144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 15 ms 6272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 15 ms 6272 KB Execution killed with signal 11 (could be triggered by violating memory limits)