Submission #244468

#TimeUsernameProblemLanguageResultExecution timeMemory
244468cheehengCalvinball championship (CEOI15_teams)C++14
100 / 100
832 ms632 KiB
#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*(long long)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 (stderr)

teams.cpp: In function 'int main()':
teams.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
teams.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...