oj.uz

Submission #162261

# Submission time Handle Problem Language Result Execution time Memory
162261 2019-11-07T11:01:38 Z dolphingarlic Calvinball championship (CEOI15_teams) C++14
20 / 100
 173 ms 672 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 = 1e9 + 7;

int a[10001], mx[10001];
ll 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;
		
		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 3 ms 504 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 256 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 256 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 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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