Submission #50467

#	Time	Username	Problem	Language	Result	Execution time	Memory
50467		top34051	Tents (JOI18_tents)	C++17	48 / 100	1140 ms	109400 KiB

tents

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 305;
const ll mod = 1e9+7;
int n,m;
ll dp[maxn][maxn][maxn];
ll add(ll x, ll y) {
    return ((x+y)%mod + mod)%mod;
}
ll mul(ll x, ll y) {
    return ((x*y)%mod + mod)%mod;
}
ll comb(ll x) {
    return ((x*(x-1)/2)%mod + mod)%mod;
}
ll f(int x, int need, int free) {
    if(x==n+1) return 1;
    if(!dp[x][need][free]) {
        ll res = 0;
        //nothing
        res = add(res, f(x+1,need,free));
        //point to south
        if(free>=1) res = add(res, mul(free, f(x+1,need+1,free-1)));
        //point to north
        if(free>=1) res = add(res, mul(free, f(x+1,need,free-1)));
        if(need>=1) res = add(res, mul(need, f(x+1,need-1,free)));
        //point to west and east
        if(free>=1) res = add(res, mul(free, f(x+1,need,free-1)));
        if(free>=1) res = add(res, mul(free, f(x+1,need,free-1)));
        if(free>=2) res = add(res, mul(comb(free), f(x+1,need,free-2)));
        dp[x][need][free] = res;
    }
    return dp[x][need][free];
}
int main() {
    scanf("%d%d",&n,&m);
    printf("%lld",add(f(1,0,m),-1));
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:37: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: 0 / 52