#include <iostream>
#include <cstring>
using namespace std;
int N;
int arr[10005];
int memo[2005][2005][2];
int dp(int idx, int num, int marker){
if(idx >= N) return 0;
if(idx == N - 1) return 1;
if(num > N) return 0;
if(memo[idx][num][marker] != -1) return memo[idx][num][marker];
int summ = 0;
for(int i = 1; i <= num + 1; i++){
if(marker){
if(i == arr[idx + 1]) summ += dp(idx + 1, max(num, i), 1);
else if (i < arr[idx + 1]) summ += dp(idx + 1, num, 0);
else break;
}
else if(i == num + 1) summ += dp(idx + 1, num + 1, 0);
else summ += dp(idx + 1, num, 0);
summ %= 1000007;
}
memo[idx][num][marker] = summ;
return summ;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
for(int i = 0; i < N; i++) cin >> arr[i];
memset(memo, -1, sizeof(memo));
cout << dp(0, 1, 1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
31692 KB |
Output is correct |
2 |
Correct |
12 ms |
31688 KB |
Output is correct |
3 |
Correct |
12 ms |
31680 KB |
Output is correct |
4 |
Correct |
12 ms |
31768 KB |
Output is correct |
5 |
Correct |
12 ms |
31692 KB |
Output is correct |
6 |
Correct |
12 ms |
31724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
31692 KB |
Output is correct |
2 |
Correct |
16 ms |
31712 KB |
Output is correct |
3 |
Correct |
12 ms |
31692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31692 KB |
Output is correct |
2 |
Correct |
13 ms |
31788 KB |
Output is correct |
3 |
Correct |
12 ms |
31692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
31732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
31692 KB |
Output is correct |
2 |
Correct |
13 ms |
31672 KB |
Output is correct |
3 |
Correct |
13 ms |
31792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
31820 KB |
Output is correct |
2 |
Correct |
152 ms |
31812 KB |
Output is correct |
3 |
Correct |
150 ms |
31820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1027 ms |
31864 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1082 ms |
31948 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1086 ms |
31888 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1082 ms |
31948 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |