oj.uz

Submission #280357

# Submission time Handle Problem Language Result Execution time Memory
280357 2020-08-22T16:43:53 Z thtsshz_bgwrswh Calvinball championship (CEOI15_teams) C++17
100 / 100
 739 ms 764 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 8 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 764 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 536 KB Output is correct
2 Correct 179 ms 512 KB Output is correct
3 Correct 179 ms 512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 640 KB Output is correct
2 Correct 739 ms 640 KB Output is correct
3 Correct 727 ms 704 KB Output is correct