oj.uz

Submission #873055

# Submission time Handle Problem Language Result Execution time Memory
873055 2023-11-14T11:41:05 Z perohero Calvinball championship (CEOI15_teams) C++17
100 / 100
 170 ms 892 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e4 + 7;
const int M = 1e6 + 7;

int a[N], kek[N], teams[N];

int add(int a, int b) {
    return a + b > M ? a + b - M : a + b;
}

int mul(int a, int b) {
    return a * 1ll * b % M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        teams[i] = teams[i - 1] + (kek[a[i]] == 0);
        if (kek[a[i]] == 0) {
            kek[a[i]] = i;
        }
    }
    int ans = 0;
    vector<vector<int>> dp(2, vector<int>(n + 1, 1));
    for (int i = n; i >= 1; --i) {
        for (int k = 0; k <= i; ++k) {
            dp[0][k] = add(mul(dp[1][k], k), dp[1][k + 1]);
        }
        for (int x = 1; x < a[i]; ++x) {
            ans = add(ans, dp[1][teams[i - 1]] + (i < kek[x]));
        }
        swap(dp[0], dp[1]);
    }
    cout << add(ans, 1) << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #5
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 #6
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 348 KB Output is correct
2 Correct 28 ms 348 KB Output is correct
3 Correct 43 ms 604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 892 KB Output is correct
2 Correct 108 ms 604 KB Output is correct
3 Correct 170 ms 712 KB Output is correct