oj.uz

Submission #958872

# Submission time Handle Problem Language Result Execution time Memory
958872 2024-04-07T02:04:23 Z Ghetto Calvinball championship (CEOI15_teams) C++17
100 / 100
 154 ms 1368 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;
}

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 568 KB Output is correct
2 Correct 40 ms 348 KB Output is correct
3 Correct 37 ms 604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 692 KB Output is correct
2 Correct 154 ms 700 KB Output is correct
3 Correct 145 ms 1368 KB Output is correct