oj.uz

Submission #1091696

# Submission time Handle Problem Language Result Execution time Memory
1091696 2024-09-21T20:01:51 Z 4QT0R Tents (JOI18_tents) C++17
48 / 100
 83 ms 55176 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll mod=1e9+7;

ll mult(ll a, ll b){
	return (a*b)%mod;
}
ll chose(ll x){
	return ((x*(x-1))/2)%mod;
}

ll dp[3003][3003];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	ll n,m;
	cin >> n >> m;
	dp[0][0]=1;
	for (ll i = 1; i<=n; i++)dp[i][0]=1;
	for (ll i = 1; i<=m; i++)dp[0][i]=1;
	for (ll i = 1; i<=n; i++){
		for (ll j = 1; j<=m; j++){
			dp[i][j]=dp[i-1][j];
			dp[i][j]+=mult(4*j,dp[i-1][j-1]);
			if (j>=2)dp[i][j]+=mult(chose(j),dp[i-1][j-2]);
			if (i>=2 && j>=1)dp[i][j]+=mult(mult(i-1,j),dp[i-2][j-1]);
		}
	}
	cout << (dp[n][m]+mod-1)%mod << '\n';
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 2312 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 1368 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 2312 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 4 ms 9592 KB Output is correct
15 Incorrect 83 ms 55176 KB Output isn't correct
16 Halted 0 ms 0 KB -