Submission #658199

#	Time	Username	Problem	Language	Result	Execution time	Memory
658199		blaze21	Calvinball championship (CEOI15_teams)	C++17	100 / 100	409 ms	668 KiB

teams

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10