oj.uz

Submission #197770

# Submission time Handle Problem Language Result Execution time Memory
197770 2020-01-22T22:37:26 Z mahmoudbadawy Calvinball championship (CEOI15_teams) C++17
70 / 100
 348 ms 772 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;
	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],(arr[i]-1)*mem[y][l][1]);
			//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],l*mem[y][l][1]);
			//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:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
teams.cpp:23: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 252 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 252 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 376 KB Output is correct
3 Correct 2 ms 376 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 380 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 416 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 6 ms 404 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 772 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -