Submission #720490

#	Time	Username	Problem	Language	Result	Execution time	Memory
720490		mariowong	Calvinball championship (CEOI15_teams)	C++14	100 / 100	186 ms	884 KiB

teams

#include <bits/stdc++.h>
const long long xmod=1000007;
using namespace std;

long long dp[10005][5],a[10005],mx[10005];
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	long long ans=1;
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=n;i++) mx[i]=max(mx[i-1],a[i]);
	for (int i=1;i<=n+1;i++) dp[i][(n+1)%2]=1;
	for (int i=n;i>=1;i--){
		ans+=(dp[mx[i-1]][(i+1)%2]*(a[i]-1))%xmod; ans%=xmod;
		for (long long j=1;j<i;j++){
			dp[j][i%2]=dp[j+1][(i+1)%2];
			dp[j][i%2]+=(j*(dp[j][(i+1)%2]))%xmod;
			dp[j][i%2]%=xmod;
		}
	}
	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