Submission #1228587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228587		kaiboy	Calvinball championship (CEOI15_teams)	C++20	100 / 100	523 ms	596 KiB

teams

#include <algorithm>
#include <iostream>

using namespace std;

const int  N = 10000;
const int MD = 1000007;

int aa[N], pp[N], ch[N], xx[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> aa[i], aa[i]--;
	for (int p = 0, i = 0; i < n; i++)
		pp[i] = p = max(p, aa[i]);
	int ans = ch[0] = xx[0] = 1;
	for (int i = n - 1; i; i--) {
		long long p = aa[i];
		for (int m = 0; m < n - i; m++, p = p * (pp[i - 1] + 1) % MD)
			ans = (ans + ch[m] * p % MD * xx[n - i - 1 - m]) % MD;
		for (int m = 0; m < n - i; m++)
			xx[n - i] = (xx[n - i] + (long long) ch[m] * xx[n - i - 1 - m]) % MD;
		for (int m = n - i; m; m--)
			ch[m] = (ch[m] + ch[m - 1]) % MD;
	}
	cout << ans << '\n';
	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: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10