Submission #219736

#	Time	Username	Problem	Language	Result	Execution time	Memory
219736		patrikpavic2	Tents (JOI18_tents)	C++17	100 / 100	245 ms	35960 KiB

tents

#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 3005;
const int MOD = 1e9 + 7;

inline int add(int A,int B){
	if(A + B >= MOD) return A + B - MOD;
	return A + B;
}

inline int mul(int A,int B){
	return (ll)A * B % MOD;
}

inline int sub(int A,int B){
	if(A - B < 0) return A - B + MOD;
	return A - B;
}

int dp[N][N], inv2 = (MOD + 1) / 2;

int f(int a,int b,int sm = 0){
	if(a < 0 || b < 0) return 0;
	if(!a) return 1;
	if(dp[a][b] != -1) return dp[a][b];
	return dp[a][b] = add(add(add(mul(f(a - 2, b - 1), (a - 1) * b), mul(f(a - 1, b - 2), b * (b - 1) / 2)), mul(4 * b, f(a - 1, b - 1))), f(a - 1, b));	
}

int main(){
	memset(dp, -1, sizeof(dp));
	int x, y; scanf("%d%d", &x, &y);
	printf("%d\n", sub(f(x, y), 1));
}

Compilation message (stderr)

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

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