Submission #1132513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132513		Kubeti	Calvinball championship (CEOI15_teams)	C++20	100 / 100	125 ms	660 KiB

teams

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 1e4 + 1, mod = 1e6 + 7;

int dp[2][nmax];
int v[nmax];

int radd(int a, int b) {
  a += b;
  if(a >= mod) {
    a -= mod;
  }
  return a;
}

int32_t main(){
  ios_base::sync_with_stdio(0);cin.tie(0);
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
  }
  dp[0][0] = 1;
  int maxx = 0, ok = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 2; j <= i; j++) {
      dp[i & 1][j] = (dp[(i - 1) & 1][j] * j + dp[(i - 1) & 1][j - 1]) % mod;
    }
    if(v[i] != 1) {
      ok = 1;
    }
    dp[i & 1][0] = 1;
    if(v[i] != 1) {
      dp[i & 1][maxx] = radd(dp[i & 1][maxx], dp[(i - 1) & 1][0] * (v[i] - 1)) % mod;
    }
    if(ok) {
      dp[i & 1][1] = 1;
    }
    maxx = max(maxx, v[i]);
  }
  int ans = 0;
  for(int j = 1; j <= n; j++) {
    ans += dp[n & 1][j];
  }
  cout << (ans + 1) % mod;
  return 0;
}

• 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