oj.uz

Submission #151072

# Submission time Handle Problem Language Result Execution time Memory
151072 2019-09-01T16:50:32 Z karma Tents (JOI18_tents) C++14
100 / 100
 313 ms 36088 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(3e3) + 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 32 ms 35708 KB Output is correct
2 Correct 32 ms 35576 KB Output is correct
3 Correct 32 ms 35576 KB Output is correct
4 Correct 32 ms 35692 KB Output is correct
5 Correct 32 ms 35576 KB Output is correct
6 Correct 32 ms 35576 KB Output is correct
7 Correct 32 ms 35576 KB Output is correct
8 Correct 33 ms 35708 KB Output is correct
9 Correct 32 ms 35576 KB Output is correct
10 Correct 33 ms 35576 KB Output is correct
11 Correct 31 ms 35576 KB Output is correct
12 Correct 34 ms 35576 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 35708 KB Output is correct
2 Correct 32 ms 35576 KB Output is correct
3 Correct 32 ms 35576 KB Output is correct
4 Correct 32 ms 35692 KB Output is correct
5 Correct 32 ms 35576 KB Output is correct
6 Correct 32 ms 35576 KB Output is correct
7 Correct 32 ms 35576 KB Output is correct
8 Correct 33 ms 35708 KB Output is correct
9 Correct 32 ms 35576 KB Output is correct
10 Correct 33 ms 35576 KB Output is correct
11 Correct 31 ms 35576 KB Output is correct
12 Correct 34 ms 35576 KB Output is correct
13 Correct 32 ms 35576 KB Output is correct
14 Correct 32 ms 35832 KB Output is correct
15 Correct 195 ms 35908 KB Output is correct
16 Correct 34 ms 35704 KB Output is correct
17 Correct 47 ms 35704 KB Output is correct
18 Correct 67 ms 35704 KB Output is correct
19 Correct 228 ms 35916 KB Output is correct
20 Correct 179 ms 35948 KB Output is correct
21 Correct 115 ms 35932 KB Output is correct
22 Correct 128 ms 35832 KB Output is correct
23 Correct 87 ms 35960 KB Output is correct
24 Correct 313 ms 35960 KB Output is correct
25 Correct 229 ms 35832 KB Output is correct
26 Correct 263 ms 36060 KB Output is correct
27 Correct 294 ms 36088 KB Output is correct