oj.uz

Submission #75858

# Submission time Handle Problem Language Result Execution time Memory
75858 2018-09-11T11:13:17 Z kdh9949 Tents (JOI18_tents) C++17
100 / 100
 280 ms 141896 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 3005;
const ll M = ll(1e9) + 7;

int n, m;
ll d[N][N], e[N][N];

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < N; i++){
        d[0][i] = e[0][i] = 1;
        d[i][0] = i + 1;
        e[i][0] = (i + 1) * (i + 2) / 2;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            d[i][j] = (4 * j * d[i - 1][j - 1] + 1) % M;
            if(j > 1) d[i][j] = (d[i][j] + j * (j - 1) / 2 * d[i - 1][j - 2]) % M;
            if(i > 1) d[i][j] = (d[i][j] + j * e[i - 2][j - 1]) % M;
            e[i][j] = (i + 1) * d[i][j] % M;
            d[i][j] = (d[i][j] + d[i - 1][j]) % M;
            e[i][j] = (e[i][j] + e[i - 1][j]) % M;
        }
    }
    printf("%lld\n", (d[n][m] - d[n - 1][m] - 1 + M) % M);
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24696 KB Output is correct
2 Correct 19 ms 24704 KB Output is correct
3 Correct 19 ms 24768 KB Output is correct
4 Correct 19 ms 24868 KB Output is correct
5 Correct 20 ms 25080 KB Output is correct
6 Correct 19 ms 25084 KB Output is correct
7 Correct 20 ms 25088 KB Output is correct
8 Correct 21 ms 25088 KB Output is correct
9 Correct 19 ms 25088 KB Output is correct
10 Correct 21 ms 25792 KB Output is correct
11 Correct 19 ms 25792 KB Output is correct
12 Correct 22 ms 26364 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24696 KB Output is correct
2 Correct 19 ms 24704 KB Output is correct
3 Correct 19 ms 24768 KB Output is correct
4 Correct 19 ms 24868 KB Output is correct
5 Correct 20 ms 25080 KB Output is correct
6 Correct 19 ms 25084 KB Output is correct
7 Correct 20 ms 25088 KB Output is correct
8 Correct 21 ms 25088 KB Output is correct
9 Correct 19 ms 25088 KB Output is correct
10 Correct 21 ms 25792 KB Output is correct
11 Correct 19 ms 25792 KB Output is correct
12 Correct 22 ms 26364 KB Output is correct
13 Correct 19 ms 26364 KB Output is correct
14 Correct 20 ms 26364 KB Output is correct
15 Correct 172 ms 112264 KB Output is correct
16 Correct 32 ms 112264 KB Output is correct
17 Correct 55 ms 112264 KB Output is correct
18 Correct 62 ms 112264 KB Output is correct
19 Correct 196 ms 126760 KB Output is correct
20 Correct 168 ms 126760 KB Output is correct
21 Correct 123 ms 126760 KB Output is correct
22 Correct 110 ms 126760 KB Output is correct
23 Correct 71 ms 126760 KB Output is correct
24 Correct 280 ms 141896 KB Output is correct
25 Correct 196 ms 141896 KB Output is correct
26 Correct 221 ms 141896 KB Output is correct
27 Correct 238 ms 141896 KB Output is correct