Submission #75858

#	Time	Username	Problem	Language	Result	Execution time	Memory
75858		kdh9949	Tents (JOI18_tents)	C++17	100 / 100	280 ms	141896 KiB

tents

#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 (stderr)

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 / 48
• Subtask 2: 52 / 52