oj.uz

Submission #162315

# Submission time Handle Problem Language Result Execution time Memory
162315 2019-11-07T14:44:09 Z dolphingarlic Calvinball championship (CEOI15_teams) C++14
100 / 100
 176 ms 716 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
typedef long long ll;
 
const ll MOD = 1e6 + 7;
 
ll a[10001], mx[10001], dp[2][10001];
 
int main() {
	int n;
	cin >> n;
	FOR(i, 0, n) {
		dp[0][i] = 1;
		cin >> a[i];
		if (i) mx[i] = max(mx[i - 1], a[i - 1]);
	}
 
	ll ans = 1;
	for (int i = n - 1; ~i; i--) {
		ans = (ans + ((a[i] - 1) * dp[0][mx[i]]) % MOD) % MOD;
		
		FOR(j, 0, i)
			dp[1][j] = (j * dp[0][j] + dp[0][j + 1]) % MOD;
		FOR(j, 0, n + 1) dp[0][j] = dp[1][j];
	}
	
	cout << ans;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 348 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 348 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 400 KB Output is correct
2 Correct 2 ms 504 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 504 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 380 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 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 632 KB Output is correct
2 Correct 176 ms 700 KB Output is correct
3 Correct 171 ms 716 KB Output is correct