Submission #1223365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223365		salmon	Tents (JOI18_tents)	C++20	100 / 100	186 ms	37168 KiB

tents

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

int H;
int W;
int memo[3100][3100];
long long int mod = 1'000'000'007;
long long int fact[3100];
long long int ifact[3100];

long long int exp(long long int v , long long int multi, long long int e){
	if(e == 0) return v;
	if(e % 2 == 1) return exp(v * multi % mod, multi * multi % mod, e / 2);
	else return exp(v, multi * multi % mod, e/ 2);
}

long long int dp(int H, int W){
	if(memo[H][W] != -1) return memo[H][W];

	if(H == 0) return memo[H][W] = 1;
	if(W == 0) return memo[H][W] = 1;
	
	if(H == 1){
		long long int V = 1;
		
		V += W * 4;
		V += W * (W - 1)/2;
		
		return memo[H][W] = V % mod;
	}
	else if(W == 1){
		long long int V = 1;
		
		V += H * 4;
		V += H * (H - 1)/2;
		
		return memo[H][W] = V % mod;
	}
	
	long long int V = dp(H - 1, W);
	
	V += W * 4 * dp(H - 1, W - 1) % mod;
	V += W * (W - 1)/2 * dp(H - 1, W - 2) % mod;
	V += (H - 1) * W * dp(H - 2, W - 1) % mod;
	
	return memo[H][W] = V % mod;
}

int main(){
	
	scanf(" %d",&H);
	scanf(" %d",&W);
	
	fact[0] = 1;
	
	for(int i = 1; i < 3100; i++){
		fact[i] = fact[i - 1] * i % mod;
	}
	
	for(int i = 0; i < 3100; i++){
		ifact[i] = exp(1,fact[i], mod - 2);
	}
	
	
	for(int i = 0; i <= H + 5; i++){
		for(int j = 0; j <= W + 5; j++){
			memo[i][j] = -1;
		}
	}
	
	printf("%lld\n",(dp(H,W) - 1  + mod) % mod);
}

Compilation message (stderr)

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

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