Submission #93781

#	Time	Username	Problem	Language	Result	Execution time	Memory
93781		combi2k2	Calvinball championship (CEOI15_teams)	C++14	100 / 100	209 ms	1016 KiB

teams

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int   N   = 1e4 + 5;
const int   mod = 1e6 + 7;

int add(int a,int b)    {
	a += b;
	if(a >= mod)a -= mod;
	return  a;
}
int sub(int a,int b)    {
	a -= b;
	if(a <  0)  a += mod;
	return  a;
}
int mul(int a,int b)    {
	return (long long)a * b % mod;
}

int a[N], maxi[N];
int f[2][N];
int g[N];
 
signed main()   {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int n;  cin >> n;
	
	fill(f[0],f[0] + 1 + n,1);  g[0] = 1;
	
	for(int i = 0 ; i < n ; ++i)    {
		cin >> a[i];
		maxi[i + 1] = max(maxi[i],a[i]);
	}
	
	for(int i = 1, p = 0 ; i < n ; ++i, p ^= 1) {
		for(int j = 0 ; j <= n && j <= maxi[n - i - 1] + n - i ; ++j)
			f[p ^ 1][j] = add(mul(f[p][j],j),f[p][j + 1]);
		g[i] = f[p ^ 1][maxi[n - i - 1]];
	}
	
	int ans = 1;
	
	for(int i = 0 ; i < n ; ++i)    ans = add(ans,mul(a[i] - 1,g[n - i - 1]));
	
	cout << ans << endl;
}

• 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