oj.uz

Submission #518428

# Submission time Handle Problem Language Result Execution time Memory
518428 2022-01-23T19:29:49 Z blue Calvinball championship (CEOI15_teams) C++17
100 / 100
 718 ms 884 KB 
#include <iostream>
using namespace std;

using ll = long long;
const ll mod = 1'000'007LL;

ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll sq(ll a)
{
    return mul(a, a);
}

ll pow(ll b, ll e)
{
    if(e == 0) return 1;
    else if(e % 2 == 0) return sq(pow(b, e/2));
    else return mul(b, pow(b, e-1));
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    ll a[1+n];
    a[0] = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];

    ll* ch[1+n];
    ch[0] = new ll[1+n];
    ch[1] = new ll[1+n];
    for(int i = 2; i <= n; i++) ch[i] = ch[i-2];

    for(int i = 0; i <= n; i++) ch[0][i] = ch[1][i] = 0;
    ch[0][0] = 1;

    ll dp[1+n];
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        dp[i] = 0;
        for(int t = 1; t <= i; t++)
        {
            // dp[i] = (dp[i] + ((dp[i-t] * ch[i-1][t-1]) % mod)) % mod;
            dp[i] = (dp[i] + ((dp[i-t] * ch[i-1][t-1]) % mod)) % mod;
        }

        ch[i][0] = ch[i][i] = 1;
        for(int j = 1; j < i; j++) ch[i][j] = (ch[i-1][j] + ch[i-1][j-1]) % mod;
    }



    ll fact[1+n];
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = mul(i, fact[i-1]);


    ll ans = 1;

    // ll q = 0;


    ll q[1+n];
    q[0] = 0;
    for(int i = 1; i <= n; i++) q[i] = max(q[i-1], a[i-1]);

    for(int i = 0; i <= n; i++) ch[0][i] = ch[1][i] = 0;


    for(int i = n; i >= 1; i--)
    {
        ch[n-i][0] = ch[n-i][n-i] = 1;
        for(int j = 1; j < n-i; j++)
            ch[n-i][j] = (ch[n-i-1][j-1] + ch[n-i-1][j]) % mod;

        ll qp = 1;

        for(int c = 0; c <= n-i; c++)
        {
            // cerr << i << ' ' << c << '\n';
            ll curr = ((ch[n-i][c] * qp * dp[n-i-c]) % mod) * (a[i]-1);
            ans = (ans + curr) % mod;

            qp = (qp * q[i]) % mod;
        }
    }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 ms 280 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 0 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 7 ms 372 KB Output is correct
3 Correct 9 ms 336 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 496 KB Output is correct
2 Correct 180 ms 580 KB Output is correct
3 Correct 165 ms 524 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 832 KB Output is correct
2 Correct 691 ms 844 KB Output is correct
3 Correct 668 ms 884 KB Output is correct