Submission #527150

#	Time	Username	Problem	Language	Result	Execution time	Memory
527150		siewjh	Calvinball championship (CEOI15_teams)	C++17	70 / 100	14 ms	8344 KiB

teams

// 70 pts
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int nums;
int arr[1005];
const int mod = 1'000'007;
int memo[1005][1005][2];
int dp(int x, int mval, bool attop) {
	if (x == nums) return 1;
	if (memo[x][mval][attop] != -1) return memo[x][mval][attop];
	int ans = 0;
	if (attop) {
		ans += dp(x + 1, max(arr[x], mval), 1);
		ans %= mod;
		ans += (arr[x] - 1) * dp(x + 1, mval, 0);
		ans %= mod;
	}
	else {
		ans += dp(x + 1, mval + 1, 0);
		ans %= mod;
		ans += mval * dp(x + 1, mval, 0);
		ans %= mod;
	}
	return memo[x][mval][attop] = ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> nums;
	for (int i = 0; i < nums; i++) cin >> arr[i];
	memset(memo, -1, sizeof(memo));
	cout << dp(1, 1, 1);
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10