Submission #1245329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245329		pasta	Calvinball championship (CEOI15_teams)	C++20	100 / 100	122 ms	636 KiB

teams

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

ll dp[2][N], a[N];

ll add(ll a, ll b){
    a += b;
    return a % mod;
}

int main(){
    ll n;
    cin>>n;
    for (int i = 1;i <= n; ++i)
		cin>>a[i];
		
    dp[0][0] = 1;
    ll mx = 0, ok = 0;
    for(ll i = 1; i <= n; ++i){
        for(ll j = 2; j <= i; ++j)
            dp[i & 1][j] = (dp[i+1&1][j] * j % mod + dp[i+1&1][j - 1]) % mod;
        if(a[i] != 1ll) 
			ok = 1;
        dp[i & 1][0] = 1;
        if(a[i] != 1ll)
            dp[i & 1][mx] = add(dp[i & 1][mx], (a[i] - 1ll) * dp[i + 1 & 1][0]) % mod;
        if(ok)
			dp[i & 1][1] = 1ll;
        mx = max(mx, a[i]);
    }
    int ans = 0;
    for(ll i = 1; i <= n;++i)
        ans = add(ans, dp[n & 1][i]);
    cout<< add(ans, 1) <<'\n';
}

• 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