oj.uz

Submission #658199

# Submission time Handle Problem Language Result Execution time Memory
658199 2022-11-12T11:19:54 Z blaze21 Calvinball championship (CEOI15_teams) C++17
100 / 100
 409 ms 668 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>
#include <iomanip>
using namespace std;

#define ll long long

const int mod = 1000007;

int main(){

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;

    vector <ll> a (n + 1), maxi (n + 1), dp (n + 1, 1);

    for(int i = 1; i <= n; i++){

        cin >> a[i];
        maxi[i] = max(maxi[i - 1], a[i]);
    }

    ll ans = 0;

    for(int i = n; i >= 1; i--){

        ans = (ans + (a[i] - 1) * dp[maxi[i - 1]]) % mod;

        vector <ll> ndp (n + 1, 0);

        for(int j = 1; j <= n; j++){

            ndp[j] = (dp[j] * j) % mod;

            if(j + 1 <= n){

                ndp[j] = (ndp[j] + dp[j + 1]) % mod;
            }
        }

        dp = ndp;
    }

    cout << (ans + 1) % mod << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 472 KB Output is correct
2 Correct 96 ms 476 KB Output is correct
3 Correct 107 ms 456 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 644 KB Output is correct
2 Correct 361 ms 648 KB Output is correct
3 Correct 409 ms 660 KB Output is correct