제출 #1011197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1011197		gyg	Calvinball championship (CEOI15_teams)	C++17	40 / 100	278 ms	600 KiB

teams

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 1e4 + 5, MOD = 1e6 + 7;

int n;
array<int, MAX_N> a;

array<bool, MAX_N> is_first;
void precomp() {
    int max_val = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] <= max_val) continue;
        max_val = a[i], is_first[i] = true; 
    }
}

array<array<int, MAX_N>, 2> dp;
int comp() {
    auto mod = [](int x) { return (x + MOD) % MOD; };
    
    int ans = 0;
    for (int s = 0; s < n; s++) {
        int p = s % 2, opp_p = (s + 1) % 2;
        for (int c = 1; c <= n + 1; c++) {
            if (s == 0) { dp[p][c] = 1; continue; }
            int leave = mod(dp[opp_p][c] * c);
            int take = dp[opp_p][c + 1];
            dp[p][c] = mod(leave + take);
        }

        int i = n - s, new_ans = 0;
        if (is_first[i]) new_ans = mod((a[i] - 1) * dp[p][a[i] - 1]);
        else new_ans = mod((a[i] - 1) * dp[p][a[i]]);
        ans = mod(ans + new_ans);
    }
    ans = mod(ans + 1);
    return ans;
}

signed main() {
    // freopen("teams.in", "r", stdin);
    cin >> n; 
    for (int i = 1; i <= n; i++) cin >> a[i];

    precomp();
    int ans = comp();
    cout << ans << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10