oj.uz

Submission #151071

# Submission time Handle Problem Language Result Execution time Memory
151071 2019-09-01T16:50:08 Z karma Tents (JOI18_tents) C++14
48 / 100
 11 ms 8440 KB 
#include <bits/stdc++.h>
#define ll      long long
#define pb      emplace_back
#define mp      make_pair
#define fi      first
#define se      second

using namespace std;

const int N = int(1e3) + 2;
const int mod = int(1e9) + 7;

int f[N][N], n, m;

int add(int& x, int y) {if((x += y) >= mod) x -= mod;}
int mul(int x, int y) {return 1ll * x * y % mod;}

int DP(int r, int c)
{
    if(f[r][c] != -1) return f[r][c];
    if(r * c == 0) return f[r][c] = 1;
    int& res = f[r][c];
    res = DP(r - 1, c); // 0 in row r
    add(res, mul(DP(r - 1, c - 1), 4 * c)); // 1 in row r
    if(r >= 2) add(res, mul(DP(r - 2, c - 1), (r - 1) * c)); // 1 in row r, 1 in (r - 1) rows, same column
    if(c >= 2) add(res, mul(DP(r - 1, c - 2), c * (c - 1) / 2)); // same row r
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    memset(&f, -1, sizeof f);
    cin >> n >> m;
    cout << (DP(n, m) - 1 + mod) % mod;
}

Compilation message

tents.cpp: In function 'int add(int&, int)':
tents.cpp:15:54: warning: no return statement in function returning non-void [-Wreturn-type]
 int add(int& x, int y) {if((x += y) >= mod) x -= mod;}
                                                      ^
tents.cpp: In function 'int main()':
tents.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 4216 KB Output is correct
8 Correct 6 ms 4220 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 7 ms 4216 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 8 ms 4344 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 5 ms 4216 KB Output is correct
3 Correct 6 ms 4344 KB Output is correct
4 Correct 6 ms 4216 KB Output is correct
5 Correct 5 ms 4216 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 4216 KB Output is correct
8 Correct 6 ms 4220 KB Output is correct
9 Correct 5 ms 4216 KB Output is correct
10 Correct 7 ms 4216 KB Output is correct
11 Correct 5 ms 4216 KB Output is correct
12 Correct 8 ms 4344 KB Output is correct
13 Correct 5 ms 4344 KB Output is correct
14 Runtime error 11 ms 8440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -