Submission #258108

#	Time	Username	Problem	Language	Result	Execution time	Memory
258108		doowey	Calvinball championship (CEOI15_teams)	C++14	100 / 100	554 ms	820 KiB

teams

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e4 + 1;
const int MOD = (int)1e6 + 7;
int dp[2][N][2];

int mult(int a, int b){
    return (a * 1ll * b) % MOD;
}

void add(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    dp[0][0][0] = 1;
    int a;
    int low;
    for(int i = 1; i <= n; i ++ ){
        cin >> a;
        for(int j = 0; j < i ; j ++ ){
            add(dp[1][j][1], mult(dp[0][j][1],j));
            add(dp[1][j+1][1],dp[0][j][1]);
            low = min(j,a-1);
            add(dp[1][j][1],mult(dp[0][j][0],low));
            if(j >= a)
                add(dp[1][j][0],dp[0][j][0]);
            if(j + 1 <= a)
                add(dp[1][j+1][(j+1)<a],dp[0][j][0]);
        }
        for(int j = 0 ; j <= i ; j ++ ){
            dp[0][j][0]=dp[1][j][0];
            dp[0][j][1]=dp[1][j][1];
            dp[1][j][0]=0;
            dp[1][j][1]=0;
        }
    }
    int ans = 0;
    for(int j = 1; j <= n; j ++ ){
        ans += dp[0][j][0] + dp[0][j][1];
        ans %= MOD;
    }
    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