Submission #1143978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143978		SuperVOI	Tents (JOI18_tents)	C++20	100 / 100	80 ms	47688 KiB

tents

#include <bits/stdc++.h>
#define ll long long
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define GETBIT(i, msk) ((msk >> (i)) & 1)

using namespace std;

const int maxn = 1e5;
const int lim  = 1e6;
const ll  mod  = 1e9 + 7;

template<class T1,class T2>
void Add(T1 &a,T2 b) {
    a += b;
    if(a < 0) a += mod;
    if(a >= mod) a -= mod;
    return;
}

inline ll readInt() {
    char c;
    while(c = getchar(), c != '-' && (c < '0' || '9' < c));
    bool sign = (c == '-');
    if(sign) c = getchar();
    ll res = c - '0';
    while(c = getchar(), '0' <= c && c <= '9') res = res * 10 + c - '0';
    return (sign ? -res : res);
}

int nRow, nCol;
int dp[5005][5005];

void solve() {
    for(int i = 0; i <= max(nRow, nCol); ++i) dp[i][0] = dp[0][i] = 1;
    for(int i = 1; i <= nRow; ++i) for(int j = 1; j <= nCol; ++j){
        Add(dp[i][j], dp[i - 1][j]);
        Add(dp[i][j], 4LL * dp[i - 1][j - 1] * j % mod);
        if(i > 1) Add(dp[i][j], 1LL * dp[i - 2][j - 1] * (i - 1) * j % mod);
        if(j > 1) Add(dp[i][j], 1LL * dp[i - 1][j - 2] * (j * (j - 1) / 2) % mod);
    }
    cout<<(dp[nRow][nCol] - 1 + mod) % mod;
    return;
}

void input() {
    nRow = readInt();
    nCol = readInt();
    return;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    input();
    solve();

    return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52