#include <bits/stdc++.h>
using namespace std;
vector<int> seq;
vector<vector<vector<int> > > dp;
int recurse(int strict, int i, int maxN) {
if (dp[strict][i][maxN] > -1) {
return dp[strict][i][maxN];
}
if (i==0) {
if (strict) return dp[strict][i][maxN] = seq[i];
else return dp[strict][i][maxN] = (maxN + 1);
}
int poss = 0;
if (strict) {
poss += recurse(1, i-1, max(seq[i], maxN));
if (seq[i]>1) poss += (seq[i]-1) * recurse(0, i-1, maxN);
} else {
poss += maxN * recurse(0, i-1, maxN);
poss += recurse(0, i-1, maxN+1);
}
dp[strict][i][maxN] = poss;
return poss;
}
int main() {
int N;cin>>N;
seq.assign(N, 0);
dp.assign(2, vector<vector<int> >(N, vector<int>(N+1, -1)));
for (int i = N-1; i >= 0; i--) {
cin >> seq[i];
}
cout << recurse(1, N-1, 1) << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
288 KB |
Output is correct |
3 |
Correct |
0 ms |
296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
39 ms |
3308 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
339 ms |
12216 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
34 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
33 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
32 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |