Submission #280357

#	Time	Username	Problem	Language	Result	Execution time	Memory
280357		thtsshz_bgwrswh	Calvinball championship (CEOI15_teams)	C++17	100 / 100	739 ms	764 KiB

teams

#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<algorithm>
using namespace std;
long long dp[2][10005]={0},num[10005],pre[10005]={0},mod=1000007;
int main(){
	long long i,j,n;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
		scanf("%lld",&num[i]);
	pre[1]=num[1];
	for(i=2;i<=n;i++)
		pre[i]=max(pre[i-1],num[i]);
	long long cur=0,ans=num[n];
	for(i=1;i<=n;i++)	
		dp[cur][i]=i+1;
	for(i=n-1;i>=1;i--){
		if(pre[i-1]>=num[i]-1)
			ans=(ans+dp[cur][pre[i-1]]*(num[i]-1))%mod;
		else{
			ans=(ans+dp[cur][pre[i-1]]*pre[i-1])%mod;
			for(j=pre[i-1]+1;j<num[i];j++)
				ans+=dp[cur][j];
			ans%=mod;
		}
		//for(j=1;j<num[i];j++)
		//	ans=(ans+dp[cur][max(pre[i-1],j)])%mod;
		cur^=1;
		for(j=1;j<=n;j++)
			dp[cur][j]=(dp[cur^1][j]*j+dp[cur^1][j+1])%mod;
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

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