oj.uz

Submission #197771

# Submission time Handle Problem Language Result Execution time Memory
197771 2020-01-22T22:39:13 Z mahmoudbadawy Calvinball championship (CEOI15_teams) C++17
100 / 100
 371 ms 888 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 720 KB Output is correct

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 724 KB Output is correct
2 Correct 371 ms 760 KB Output is correct
3 Correct 371 ms 888 KB Output is correct