Submission #50492

#	Time	Username	Problem	Language	Result	Execution time	Memory
50492		top34051	Tents (JOI18_tents)	C++17	100 / 100	929 ms	59460 KiB

tents

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

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:39: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