Submission #163881

#	Time	Username	Problem	Language	Result	Execution time	Memory
163881		arnold518	Tents (JOI18_tents)	C++14	100 / 100	86 ms	71004 KiB

tents

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3000;
const ll MOD = 1e9+7;

int H, W;
ll dp[MAXN+10][MAXN+10];

int main()
{
	int i, j;
	scanf("%d%d", &H, &W);

	for(i=0; i<=H; i++) dp[i][0]=1;
	for(i=0; i<=W; i++) dp[0][i]=1;

	for(i=0; i<=H; i++) dp[i][1]=(ll)i*(i-1)/2+4*i+1, dp[i][1]%=MOD;
	for(i=0; i<=W; i++) dp[1][i]=(ll)i*(i-1)/2+4*i+1, dp[1][i]%=MOD;

	for(i=2; i<=H; i++)
	{
		for(j=2; j<=W; j++)
		{
			dp[i][j]=dp[i-1][j]+(ll)j*(j-1)/2*dp[i-1][j-2]+(ll)(i-1)*j*dp[i-2][j-1]+(ll)4*j*dp[i-1][j-1];
			dp[i][j]%=MOD;
		}
	}
	dp[H][W]+=MOD-1;
	dp[H][W]%=MOD;
	printf("%lld", dp[H][W]);
}

Compilation message (stderr)

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