oj.uz

Submission #225077

# Submission time Handle Problem Language Result Execution time Memory
225077 2020-04-19T09:14:25 Z kartel Mobitel (COCI19_mobitel) C++14
0 / 130
 140 ms 6016 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(301)
#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][1005][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;
}

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][1][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 14 ms 6016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 15 ms 6016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 126 ms 2168 KB Output isn't correct
4 Incorrect 135 ms 2048 KB Output isn't correct
5 Incorrect 140 ms 2048 KB Output isn't correct
6 Incorrect 136 ms 2048 KB Output isn't correct
7 Incorrect 67 ms 1536 KB Output isn't correct
8 Runtime error 12 ms 5760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 14 ms 6016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 15 ms 6016 KB Execution killed with signal 11 (could be triggered by violating memory limits)