oj.uz

Submission #154631

# Submission time Handle Problem Language Result Execution time Memory
154631 2019-09-23T11:04:29 Z TadijaSebez Calvinball championship (CEOI15_teams) C++11
100 / 100
 975 ms 632 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 476 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 504 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 508 KB Output is correct
2 Correct 51 ms 528 KB Output is correct
3 Correct 51 ms 520 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 532 KB Output is correct
2 Correct 100 ms 504 KB Output is correct
3 Correct 99 ms 504 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 608 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 560 KB Output is correct
2 Correct 496 ms 548 KB Output is correct
3 Correct 490 ms 632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 584 KB Output is correct
2 Correct 975 ms 632 KB Output is correct
3 Correct 967 ms 596 KB Output is correct