oj.uz

Submission #48446

# Submission time Handle Problem Language Result Execution time Memory
48446 2018-05-13T15:30:53 Z IvanC Calvinball championship (CEOI15_teams) C++17
100 / 100
 424 ms 1052 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 556 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 2 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 796 KB Output is correct
2 Correct 8 ms 828 KB Output is correct
3 Correct 8 ms 844 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 876 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 900 KB Output is correct
2 Correct 133 ms 900 KB Output is correct
3 Correct 134 ms 900 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 924 KB Output is correct
2 Correct 370 ms 960 KB Output is correct
3 Correct 424 ms 1052 KB Output is correct