oj.uz

Submission #720490

# Submission time Handle Problem Language Result Execution time Memory
720490 2023-04-08T11:05:04 Z mariowong Calvinball championship (CEOI15_teams) C++14
100 / 100
 186 ms 884 KB 
#include <bits/stdc++.h>
const long long xmod=1000007;
using namespace std;

long long dp[10005][5],a[10005],mx[10005];
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	long long ans=1;
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=n;i++) mx[i]=max(mx[i-1],a[i]);
	for (int i=1;i<=n+1;i++) dp[i][(n+1)%2]=1;
	for (int i=n;i>=1;i--){
		ans+=(dp[mx[i-1]][(i+1)%2]*(a[i]-1))%xmod; ans%=xmod;
		for (long long j=1;j<i;j++){
			dp[j][i%2]=dp[j+1][(i+1)%2];
			dp[j][i%2]+=(j*(dp[j][(i+1)%2]))%xmod;
			dp[j][i%2]%=xmod;
		}
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 852 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 596 KB Output is correct
2 Correct 43 ms 604 KB Output is correct
3 Correct 44 ms 624 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 884 KB Output is correct
2 Correct 186 ms 852 KB Output is correct
3 Correct 168 ms 852 KB Output is correct