oj.uz

Submission #958866

# Submission time Handle Problem Language Result Execution time Memory
958866 2024-04-07T01:53:35 Z Ghetto Calvinball championship (CEOI15_teams) C++17
70 / 100
 52 ms 65536 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39260 KB Output is correct
2 Correct 5 ms 39260 KB Output is correct
3 Correct 5 ms 39256 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65116 KB Output is correct
2 Correct 29 ms 65112 KB Output is correct
3 Correct 11 ms 65116 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -