oj.uz

Submission #225101

# Submission time Handle Problem Language Result Execution time Memory
225101 2020-04-19T09:25:31 Z kartel Mobitel (COCI19_mobitel) C++14
0 / 130
 144 ms 6400 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;}

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

int C(int n, int 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
0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 6400 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 124 ms 2048 KB Output isn't correct
4 Incorrect 140 ms 2176 KB Output isn't correct
5 Incorrect 144 ms 2176 KB Output isn't correct
6 Incorrect 135 ms 2176 KB Output isn't correct
7 Incorrect 67 ms 1536 KB Output isn't correct
8 Runtime error 13 ms 6144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 17 ms 6272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 16 ms 6376 KB Execution killed with signal 11 (could be triggered by violating memory limits)