Submission #153362

#	Time	Username	Problem	Language	Result	Execution time	Memory
153362		junodeveloper	Tents (JOI18_tents)	C++14	100 / 100	169 ms	35776 KiB

tents

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD=1e9+7;
int H,W;
int dp[3010][3010];
inline void add(int& a,int b) {
	a+=b;a%=MOD;
}
int main() {
	scanf("%d%d",&H,&W);
	int h,w;
	dp[0][0]=1;
	for(h=1;h<=H;h++) dp[h][0]=1;
	for(w=1;w<=W;w++) dp[0][w]=1;
	dp[1][1]=5;
	for(h=1;h<=H;h++) dp[h][1]=(h*4+h*(h-1)/2+1)%MOD;
	for(w=1;w<=W;w++) dp[1][w]=(w*4+w*(w-1)/2+1)%MOD;
	for(h=2;h<=H;h++) {
		for(w=2;w<=W;w++) {
			add(dp[h][w],dp[h-1][w]);
			add(dp[h][w],4ll*w*dp[h-1][w-1]%MOD);
			add(dp[h][w],(ll)w*(h-1)*dp[h-2][w-1]%MOD);
			add(dp[h][w],(ll)w*(w-1)/2%MOD*dp[h-1][w-2]%MOD);
		}
	}
	printf("%d",(MOD-1+dp[H][W])%MOD);
	return 0;
}

Compilation message (stderr)

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

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