Submission #569943

#	Time	Username	Problem	Language	Result	Execution time	Memory
569943		600Mihnea	Calvinball championship (CEOI15_teams)	C++17	70 / 100	183 ms	65536 KiB

teams

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int M =  1000007;

int add(int a, int b) {
  a += b;
  if (a >= M) return a - M;
  if (a < 0) return a + M;
  return a;
}

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

void addup(int &a, int b) {
  a = add(a, b);
}

void mulup(int &a, int b) {
  a = mul(a, b);
}

const int N = 10000 + 7;
int n, a[N], mx = 0, ways[N][N]; /// ways[length left][current max]

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

///  freopen ("input.txt", "r", stdin);

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (a[i] > mx) {
      assert(a[i] == mx + 1);
      mx = a[i];
    }
  }

  for (int mx = 1; mx <= n; mx++) {
    ways[0][mx] = 1;
  }

  for (int len = 1; len <= n; len++) {
    for (int mx = 1; mx <= n; mx++) {
      /// ways[len][mx]
      ways[len][mx] = add(mul(mx, ways[len - 1][mx]), ways[len - 1][mx + 1]);
    }
  }


  int sol = 1;

  mx = 0;
  for (int i = 1; i <= n; i++) {
    for (int pl = 1; pl < a[i]; pl++) {
      addup(sol, ways[n - i][mx]);
    }
    mx = max(mx, a[i]);
  }
  cout << sol << "\n";
}

• 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: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10