oj.uz

답안 #225101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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)