Submission #1121880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121880		coolboy19521	Calvinball championship (CEOI15_teams)	C++17	100 / 100	752 ms	848 KiB

teams

#include"bits/stdc++.h"
using namespace std;

using ll = long long;

#define int ll

const int md = 1000007;
const int mxN = 10004;

int dp[2][mxN];
int a[mxN];
int p[mxN];
int d[mxN];

main() {
    int N;
    cin >> N;

    for (int i = 1; i <= N; i ++) {
        cin >> a[i];
    }

    for (int i = 1; i <= N; i ++) {
        p[i] = max(p[i - 1], a[i - 1]);
    }

    int ans = 0;
    dp[1][N + 1] = 1;
    for (int j = N; 1 <= j; j --) {
        for (int i = N; 1 <= i; i --) {
            if (j <= i) {
                dp[0][i] = (dp[0][i] + 1ll * dp[0][i + 1] * j % md) % md;
                dp[0][i] = (dp[0][i] + 1ll * dp[1][i + 1]) % md;
                if (j == p[i]) {
                    d[i] = dp[0][i];
                }
                if (j < a[i]) {
                    if (j <= p[i]) {
                        ans = (0ll + ans + d[i]);
                    } else {
                        ans = (0ll + ans + dp[0][i]);
                    }
                }
            }
        }
        swap(dp[0], dp[1]);
        dp[1][N + 1] = 1;
        memset(dp[0], 0, sizeof(dp[0]));
    }

    cout << (ans + 1ll) % md << endl;
}

Compilation message (stderr)

teams.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main() {
      | ^~~~

• 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