oj.uz

Submission #527150

# Submission time Handle Problem Language Result Execution time Memory
527150 2022-02-17T02:48:33 Z siewjh Calvinball championship (CEOI15_teams) C++17
70 / 100
 14 ms 8344 KB 
// 70 pts
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int nums;
int arr[1005];
const int mod = 1'000'007;
int memo[1005][1005][2];
int dp(int x, int mval, bool attop) {
	if (x == nums) return 1;
	if (memo[x][mval][attop] != -1) return memo[x][mval][attop];
	int ans = 0;
	if (attop) {
		ans += dp(x + 1, max(arr[x], mval), 1);
		ans %= mod;
		ans += (arr[x] - 1) * dp(x + 1, mval, 0);
		ans %= mod;
	}
	else {
		ans += dp(x + 1, mval + 1, 0);
		ans %= mod;
		ans += mval * dp(x + 1, mval, 0);
		ans %= mod;
	}
	return memo[x][mval][attop] = ans;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> nums;
	for (int i = 0; i < nums; i++) cin >> arr[i];
	memset(memo, -1, sizeof(memo));
	cout << dp(1, 1, 1);
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8292 KB Output is correct
2 Correct 14 ms 8296 KB Output is correct
3 Correct 13 ms 8296 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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