oj.uz

Submission #68610

# Submission time Handle Problem Language Result Execution time Memory
68610 2018-08-17T14:20:42 Z Googal Calvinball championship (CEOI15_teams) C++14
100 / 100
 165 ms 1244 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e4 + 1;
const int M = 1e6 + 7;
 
int n, r, a[N], m[N], d[2][N];
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        m[i] = max(m[i - 1], a[i]);
    }
    fill(d[0], d[0] + N, 1);
    r = a[n];
    for(int i = n - 1, p = 1; i >= 1; i--, p ^= 1){
        for(int j = 1; j <= i; j++)
            d[p][j] = (d[!p][j + 1] + 1LL * j * d[!p][j]) % M;  
        r = (r + 1LL * (a[i] - 1) * d[p][m[i - 1]]) % M;
    }
    cout << r % M << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 2 ms 768 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 892 KB Output is correct
2 Correct 4 ms 892 KB Output is correct
3 Correct 4 ms 928 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 948 KB Output is correct
2 Correct 31 ms 948 KB Output is correct
3 Correct 32 ms 1048 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1068 KB Output is correct
2 Correct 121 ms 1204 KB Output is correct
3 Correct 165 ms 1244 KB Output is correct