제출 #475442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
475442		MohamedAhmed04	Calvinball championship (CEOI15_teams)	C++14	100 / 100	361 ms	496 KiB

teams

#include <bits/stdc++.h>

using namespace std ;

const int mod = 1000007 ;

int Add(int x , int y)
{
	int z = x + y ;
	if(z >= mod)
		z -= mod ;
	return z ;
}

int Mul(int x , int y)
{
	return (1ll * x * y) % mod ;
}

const int MAX = 1e4 + 10 ;

int arr[MAX] ;
int n ;

int dp[2][MAX] , val[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	val[0] = 1 ; 
	for(int i = 1 ; i <= n ; ++i)
		val[i] = max(val[i-1] , arr[i]) ;
	for(int j = 1 ; j <= n ; ++j)
		dp[(n+1)&1][j] = 1 ;
	int ans = 0 ;
	for(int i = n ; i >= 1 ; --i)
	{
		int now = (i&1) ;
		int nxt = !now ;
		for(int j = 1 ; j <= n ; ++j)
			dp[now][j] = Add(Mul(j , dp[nxt][j]) , dp[nxt][j+1]) ;
		ans = Add(ans , Mul(arr[i]-1 , dp[nxt][val[i-1]])) ;
	}
	ans = Add(ans , 1) ;
	return cout<<ans<<"\n" , 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