# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244464 | 2020-07-04T06:36:10 Z | cheeheng | Calvinball championship (CEOI15_teams) | C++14 | 775 ms | 632 KB |
#include <bits/stdc++.h> using namespace std; const int MOD = 1000007; int A[10005]; int dp[2][10005][2]; int prefixMax[10005]; int n; /* int dp(int i, int cur_max, int same_so_far){ if(i == n){ return 1; }else if(memo[i][cur_max][same_so_far] != -1){ return memo[i][cur_max][same_so_far]; }else{ long long ans = 0; if(same_so_far){ for(int j = 1; j <= A[i]; j ++){ ans += dp(i+1, max(cur_max, j), j == A[i]); } }else{ for(int j = 1; j <= cur_max+1; j ++){ ans += dp(i+1, max(cur_max, j), 0); } } return memo[i][cur_max][same_so_far] = ans%MOD; } }*/ int main(){ scanf("%d", &n); prefixMax[0] = 0; for(int i = 0; i < n; i ++){ scanf("%d", &A[i]); prefixMax[i+1] = max(prefixMax[i], A[i]); } for(int i = n; i >= 0; i --){ //long long prefix_sum = dp[(i+1)&1][max(cur_max, 0)][0]; for(int cur_max = 0; cur_max <= n; cur_max ++){ for(int same_so_far = 0; same_so_far < 2; same_so_far ++){ if(i == n){ dp[i&1][cur_max][same_so_far] = 1; }else{ long long ans = 0; if(same_so_far){ if(cur_max == prefixMax[i]){ for(int j = 1; j <= A[i]; j ++){ ans += dp[(i+1)&1][max(cur_max, j)][j == A[i]]; } } }else{ //prefix_sum += dp[(i+1)&1][max(cur_max, 0)][0]; ans = cur_max*dp[(i+1)&1][cur_max][0] + dp[(i+1)&1][cur_max+1][0]; /*for(int j = 1; j <= cur_max+1; j ++){ ans += dp[(i+1)&1][max(cur_max, j)][0]; }*/ } dp[i&1][cur_max][same_so_far] = ans%MOD; } } } } printf("%d", dp[0][0][1]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 4 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 256 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 384 KB | Output is correct |
2 | Correct | 6 ms | 384 KB | Output is correct |
3 | Correct | 6 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 384 KB | Output is correct |
2 | Correct | 11 ms | 384 KB | Output is correct |
3 | Correct | 12 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 775 ms | 632 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 184 ms | 484 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 735 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |