oj.uz

Submission #225079

# Submission time Handle Problem Language Result Execution time Memory
225079 2020-04-19T09:16:12 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(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][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;
}

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 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 129 ms 2272 KB Output isn't correct
4 Incorrect 141 ms 2048 KB Output isn't correct
5 Incorrect 139 ms 2048 KB Output isn't correct
6 Incorrect 137 ms 2048 KB Output isn't correct
7 Incorrect 68 ms 1536 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 16 ms 6144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 15 ms 6144 KB Execution killed with signal 11 (could be triggered by violating memory limits)