Submission #958866

#	Time	Username	Problem	Language	Result	Execution time	Memory
958866		Ghetto	Calvinball championship (CEOI15_teams)	C++17	70 / 100	52 ms	65536 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;
}

lint dp[MAX_N][MAX_N];
void precomp() {
    for (int s = n; s >= 1; s--) {
        for (int t = 1; t <= s; t++) {
            if (s == n) dp[s][t] = 1;
            else dp[s][t] = mod(dp[s + 1][t + 1] + mod(t * dp[s + 1][t]));
        }
    }
}

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

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

    precomp();

    set<int> unis;
    lint ans = 0;
    for (int i = 1; i <= n; i++) {
        lint n_unis = unis.size();
        ans = mod(ans + mod(dp[i][n_unis] * (arr[i] - 1))); // Should be fine if n_unis = 0

        unis.insert(arr[i]);
    }
    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: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10