Submission #1122263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122263		I_love_Banu	Calvinball championship (CEOI15_teams)	C++14	100 / 100	749 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:5: 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