oj.uz

Submission #86280

# Submission time Handle Problem Language Result Execution time Memory
86280 2018-11-25T21:41:16 Z rzbt Calvinball championship (CEOI15_teams) C++14
100 / 100
 417 ms 1068 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAXN = 10010;
const ll MOD =  1000007LL;
 
ll dp[2][MAXN];
ll tot;
int N,vetor[MAXN];
 
ll solve(int pos,int maior){
	if(dp[pos][maior] != -1) return dp[pos][maior];
	if(pos == N + 1){
		return dp[pos][maior] = 1;
	}
	ll ans = 1LL*(maior - 1)*solve(pos+1,maior);
	ans += solve(pos+1,maior+1);
	return dp[pos][maior] = (int)(ans % MOD);
}
 
int main(){
	cin >> N;
	for(int i = 1;i<=N;i++) cin >> vetor[i];
	for(int i = 1;i<=N+2;i++) dp[0][i] = 1;
	for(int i = N;i>=1;i--){
		int maior = 0;
		for(int j = 1;j<i;j++) maior = max(maior,vetor[j]);
		swap(dp[0],dp[1]);
		for(int j = 1;j<=N+1;j++){
			dp[0][j] = (j-1)*dp[1][j] + dp[1][j+1];
			dp[0][j] %= MOD;
		}
		for(int j = 1;j<vetor[i];j++){
			tot += dp[1][max(j,maior) + 1];
		}
		tot %= MOD;
	}
	tot++;
	tot %= MOD;
	cout << tot << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 740 KB Output is correct
2 Correct 4 ms 744 KB Output is correct
3 Correct 3 ms 748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 752 KB Output is correct
2 Correct 8 ms 756 KB Output is correct
3 Correct 8 ms 760 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 764 KB Output is correct
2 Correct 16 ms 768 KB Output is correct
3 Correct 16 ms 816 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 944 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 944 KB Output is correct
2 Correct 117 ms 996 KB Output is correct
3 Correct 129 ms 996 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 996 KB Output is correct
2 Correct 379 ms 996 KB Output is correct
3 Correct 417 ms 1068 KB Output is correct