Submission #253392

#	Time	Username	Problem	Language	Result	Execution time	Memory
253392		ChrisT	Tents (JOI18_tents)	C++17	100 / 100	381 ms	36092 KiB

tents

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#define ree(x) ((x-1)*(x-2)/2)
const int MN = 5e5+3, MK = 1001, MOD = 1e9+7;
mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());
int dp[3005][3005];
void uadd (int &a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
}
int recur (int h, int w) {
	if(h<0||w<0) return 0;
	if (h<1||w<1) return 1;
	if (h==1&&w==1) return 5;
	if (~dp[h][w]) return dp[h][w];
	int ret = 0;
	uadd(ret,4LL*recur(h-1,w-1)%MOD);
	uadd(ret,(w-1)*1LL*recur(h-1,w-2)%MOD);
	uadd(ret,(h-1)*1LL*recur(h-2,w-1)%MOD);
	uadd(ret,recur(h-1,w));
	uadd(ret,(w-1)*4LL%MOD*recur(h-1,w-1)%MOD);
	uadd(ret,(w-1)*1LL*(h-1)%MOD*recur(h-2,w-1)%MOD);
	uadd(ret,(w-1)*1LL*(w-2)/2%MOD*recur(h-1,w-2)%MOD);
	return dp[h][w] = ret;
}
int main() {
	memset(dp,-1,sizeof dp);
	int h,w;
	scanf ("%d %d",&h,&w);
	int ret = recur(h,w)-1;
	if (ret < 0)ret += MOD;
	printf ("%d\n",ret);
    return 0;
}

Compilation message (stderr)

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