oj.uz

Submission #52539

# Submission time Handle Problem Language Result Execution time Memory
52539 2018-06-26T06:56:18 Z Alexa2001 Calvinball championship (CEOI15_teams) C++17
100 / 100
 239 ms 1276 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Mod = 1e6 + 7, Nmax = 10005;

int n, i, now, old, C;
int mx[Nmax], a[Nmax], dp[2][Nmax];
ll ans = 1;

void advance_dp()
{
    swap(now, old);
    int i;
    for(i=0; i<=n; ++i)
        dp[now][i] = ( (ll) dp[old][i] * i + dp[old][i+1] ) % Mod;
}

void init_dp()
{
    now = 0, old = 1;
    int i;
    for(i=0; i<=n; ++i)
        dp[now][i] = 1;
}

int main()
{
   // freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i)
    {
        cin >> a[i];
        mx[i] = max(mx[i-1], a[i]);
    }

    init_dp();
    for(i=n; i; --i)
    {
        C = mx[i-1];
        ans += (ll) dp[now][C] * (a[i] - 1);
        ans %= Mod;

        advance_dp();
    }

    cout << ans << '\n';
    return 0;
}

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 376 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 2 ms 756 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 756 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 768 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1016 KB Output is correct
2 Correct 68 ms 1024 KB Output is correct
3 Correct 60 ms 1060 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 1156 KB Output is correct
2 Correct 225 ms 1156 KB Output is correct
3 Correct 239 ms 1276 KB Output is correct