Submission #353535

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
353535	2021-01-21T08:20:24 Z	shivensinha4	Tents (JOI18_tents)	C++17	48 / 100	659 ms	213740 KB

tents

#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const ll mod = 1e9+7;

ll ncr(ll n, ll r) {
	if (r == 0) return 1;
	if (r == 1) return n;
	if (r == 2) return ((n*(n-1))/2 % mod);
	assert(false);
}

int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m; cin >> n >> m;
	ll dp[n+1][m+1][m+1]; // [row][empty][light]
	memset(dp, 0, sizeof(dp));
	
	vector<ll> tp(m+1);
	tp[0] = 1;
	for_(i, 1, tp.size()) tp[i] = (4*tp[i-1]) % mod;
	for_(i, 0, m+1) for_(j, 0, m+1) if (j+i <= m) dp[n][i][j] = tp[j];
	for (int i = n-1;  i >= 0; i--) {
//		cout << i << ": " << endl;
		for_(emp, 0, m+1) for_(lt, 0, m+1) if (emp+lt <= m) {
			for_(empTake, 0, min(emp, 2)+1) for_(ltTake, 0, min(lt, 1)+1) {
				if ((ltTake and empTake)) continue;
				dp[i][emp][lt] += (((ncr(emp, empTake) * ncr(lt, ltTake)) % mod) * dp[i+1][emp-empTake][lt-ltTake+(empTake == 2 ? 0 : empTake)]) % mod;
				if (dp[i][emp][lt] >= mod) dp[i][emp][lt] -= mod;
			}
//			cout << "empty: " << emp << " light: " << lt << " -> " << dp[i][emp][lt] << endl;
		}
	}
	
	cout << (dp[0][m][0]-1+mod) % mod << endl;
	
	
	return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	2 ms	1132 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	103 ms	32492 KB	Output is correct
6	Correct	45 ms	14316 KB	Output is correct
7	Correct	113 ms	35308 KB	Output is correct
8	Correct	21 ms	7020 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	136 ms	44652 KB	Output is correct
11	Correct	25 ms	8172 KB	Output is correct
12	Correct	659 ms	213740 KB	Output is correct

Subtask #2

0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	2 ms	1132 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	103 ms	32492 KB	Output is correct
6	Correct	45 ms	14316 KB	Output is correct
7	Correct	113 ms	35308 KB	Output is correct
8	Correct	21 ms	7020 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	136 ms	44652 KB	Output is correct
11	Correct	25 ms	8172 KB	Output is correct
12	Correct	659 ms	213740 KB	Output is correct
13	Correct	101 ms	53356 KB	Output is correct
14	Correct	1 ms	492 KB	Output is correct
15	Runtime error	1 ms	492 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-