Submission #337793

#	Time	Username	Problem	Language	Result	Execution time	Memory
337793		er888kh	Tents (JOI18_tents)	C++17	100 / 100	366 ms	71296 KiB

tents

#include <bits/stdc++.h>

using namespace std;

#define ALL(iter) (iter).begin(),(iter).end()

typedef int64_t s64;
typedef pair<int, int> pii;
typedef pair<s64, s64> pll;

#define F first
#define S second

#define MAXN 3003

s64 mem[MAXN][MAXN];

const int md = 1e9 + 7;

inline s64 binom(int n){
	return ((n * 1LL * (n-1)) >> 1) % md;
}

s64 dp(int h, int w){
	if(h < 0 || w < 0){
		return 0;
	}
	if(h == 0 || w == 0){
		return 1;
	}
	if(mem[h][w] != -1){
		return mem[h][w];
	}
	s64 sm = dp(h-1, w); //do nothing
	sm += binom(w) * dp(h-1, w-2);
	sm %= md;
	sm += 4 * w * dp(h-1, w-1);
	sm %= md;
	sm += (h-1) * w * dp(h-2, w-1);
	sm %= md;
	return mem[h][w] = sm;
}

int main(){
	for(int i = 0; i < MAXN; i++){
		fill(mem[i], mem[i]+MAXN, -1);
	}
	int h, w;
	scanf("%d%d", &h, &w);
	printf("%lld\n", (dp(h, w) - 1 + md) % md);
	return 0;
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:50:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 's64' {aka 'long int'} [-Wformat=]
   50 |  printf("%lld\n", (dp(h, w) - 1 + md) % md);
      |          ~~~^     ~~~~~~~~~~~~~~~~~~~~~~~~
      |             |                         |
      |             long long int             s64 {aka long int}
      |          %ld
tents.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d%d", &h, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~

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