Submission #958872

#	Time	Username	Problem	Language	Result	Execution time	Memory
958872		Ghetto	Calvinball championship (CEOI15_teams)	C++17	100 / 100	154 ms	1368 KiB

teams

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

int n;
int arr[MAX_N];

lint mod(lint x) {
    return x % MOD;
}

int n_unis[MAX_N]; // [1, i - 1]
void precomp() {
    set<int> unis;
    for (int i = 1; i <= n; i++) {
        n_unis[i] = unis.size();
        unis.insert(arr[i]);
    }
}

lint dp[2][MAX_N];

int main() {
    // freopen("calvin.in", "r", stdin);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    precomp();

    lint ans = 0;
    for (int s = n; s >= 1; s--) {
        int p = s % 2, opp_p = (s + 1) % 2;

        for (int t = 1; t <= s; t++) {
            if (s == n) dp[p][t] = 1;
            else dp[p][t] = mod(dp[opp_p][t + 1] + mod(t * dp[opp_p][t]));
        }

        ans = mod(ans + mod(dp[p][n_unis[s]] * (arr[s] - 1)));
    }
    ans++;
    cout << ans << '\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