Submission #47975

#	Time	Username	Problem	Language	Result	Execution time	Memory
47975		Extazy	Calvinball championship (CEOI15_teams)	C++17	100 / 100	137 ms	1096 KiB

teams

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 10007;
const int MOD = (1e6) + 7;

int n,a[N],pos,cnt;
int dp[2][N];
int state_cnt[N],state_coef[N];
long long ans;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i;

  scanf("%d", &n);
  for(i=1;i<=n;i++) {
    scanf("%d", &a[i]);
  }

  ans=1;

  cnt=1;
  for(pos=2;pos<=n;pos++) {
    if(a[pos]>cnt) {
      state_cnt[pos]=cnt;
      state_coef[pos]=cnt;
      
      ++cnt;
    }
    else {
      state_cnt[pos]=cnt;
      state_coef[pos]=a[pos]-1;
    }
  }

  for(cnt=0;cnt<=n;cnt++) {
    dp[(n+1)&1][cnt]=1;
  }
  for(pos=n;pos>=2;pos--) {
    ans+=dp[(pos+1)&1][state_cnt[pos]]*1ll*state_coef[pos]%MOD;
    for(cnt=1;cnt<pos;cnt++) {
      dp[pos&1][cnt]=(dp[(pos+1)&1][cnt+1]+dp[(pos+1)&1][cnt]*1ll*cnt)%MOD;
    }
  }
  
  ans%=MOD;
  printf("%lld\n", ans);

  return 0;
}

Compilation message (stderr)

teams.cpp: In function 'int main()':
teams.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
teams.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &a[i]);
     ~~~~~^~~~~~~~~~~~~

• 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