Submission #197771

#	Time	Username	Problem	Language	Result	Execution time	Memory
197771		mahmoudbadawy	Calvinball championship (CEOI15_teams)	C++17	100 / 100	371 ms	888 KiB

teams

#include <bits/stdc++.h>

using namespace std;

const int N=1e4+5,MOD=1e6+7;

long long mem[2][N][2];
int arr[N];
int n;

inline int add(int x,int y)
{
	x=x+y;
	//x%=MOD;
	if(x<0) return x+MOD;
	if(x>=MOD) return x-MOD;
	return x;
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	for(int i=1;i<=n+1;i++)
		mem[n%2][i][0]=mem[n%2][i][1]=1;
	for(int i=n-1;i>=0;i--)
	{
		for(int l=1;l<=i+1;l++)
		{
			// s=0
			// go with the same digit
			int x=i&1; int y=x^1;
			mem[x][l][0]=mem[y][max(l,arr[i])][0];
			// go with smaller digit
			mem[x][l][0]=add(mem[x][l][0],(1LL*(arr[i]-1)*mem[y][l][1])%MOD);
			//if(l<arr[i]) mem[x][l][0]=0;
			// s=1
			// increase l
			mem[x][l][1]=mem[y][l+1][1];
			// same l
			mem[x][l][1]=add(mem[x][l][1],(1LL*l*mem[y][l][1])%MOD);
			//cout << i << " " << l << " " << mem[x][l][0] << " " << mem[x][l][1] << endl;
		}
	}
	printf("%lld\n",mem[0][1][0]);
}

Compilation message (stderr)

teams.cpp: In function 'int main()':
teams.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
teams.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&arr[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