Submission #154631

#	Time	Username	Problem	Language	Result	Execution time	Memory
154631		TadijaSebez	Calvinball championship (CEOI15_teams)	C++11	100 / 100	975 ms	632 KiB

teams

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e6+7;
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int mul(int x, int y){ return (ll)x*y%mod;}
const int N=10050;
int dp[N][2],tmp[N][2];
void CL(int a[N][2])
{
	for(int i=0;i<N;i++) a[i][0]=a[i][1]=0;
}
int a[N];
int main()
{
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]);
	CL(dp);
	dp[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<N;j++) tmp[j][0]=dp[j][0],tmp[j][1]=dp[j][1];
		CL(dp);
		for(int j=0;j<N-1;j++)
		{
            int ways=min(j,a[i]-1);
            dp[j][0]=add(dp[j][0],mul(tmp[j][1],ways));
            dp[j][0]=add(dp[j][0],mul(tmp[j][0],j));
            if(a[i]<=j) dp[j][1]=add(dp[j][1],tmp[j][1]);
			if(a[i]==j+1) dp[j+1][1]=add(dp[j+1][1],tmp[j][1]);
			dp[j+1][0]=add(dp[j+1][0],tmp[j][0]);
			if(a[i]>j+1) dp[j+1][0]=add(dp[j+1][0],tmp[j][1]);
		}
	}
	int ans=1;
	for(int j=0;j<N;j++) ans=add(ans,dp[j][0]);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

teams.cpp: In function 'int main()':
teams.cpp:30:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
             if(a[i]<=j) dp[j][1]=add(dp[j][1],tmp[j][1]);
             ^~
teams.cpp:31:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
    if(a[i]==j+1) dp[j+1][1]=add(dp[j+1][1],tmp[j][1]);
    ^~
teams.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
teams.cpp:18:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&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