Submission #43835

#TimeUsernameProblemLanguageResultExecution timeMemory
43835PowerOfNinjaGoCalvinball championship (CEOI15_teams)C++14
100 / 100
520 ms1096 KiB
//Power Of Ninja Go #include <bits/stdc++.h> //#ifdef atom #else #endif using namespace std; typedef long long ll; typedef pair<int, int> ii; #define X first #define Y second #define vi vector<int> #define vii vector< ii > #define pb push_back const int md = 1e6+7; void add(int &a, int b) { a += b; if(a>= md) a -= md; } int mul(int a, int b) { return (1LL*a*b)%md; } const int maxn = 1e4+5; int arr[maxn]; int dp[2][maxn]; int k[maxn]; int main() { //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif int n; scanf("%d", &n); //while(1) { for(int i = 1; i<= n; i++) scanf("%d", &arr[i]); for(int i = 1; i<= n; i++) k[i] = max(k[i-1], arr[i-1]); for(int i = 1; i<= n+1; i++) dp[(n+1)%2][i] = 1; int ans = 0; for(int i = n; i>= 1; i--) { int f = i%2; for(int j = 0; j<= i; j++) { dp[f][j] = dp[1-f][j+1]; add(dp[f][j], mul(j, dp[1-f][j])); //printf("dp[%d][%d] = %d\n", i, j, dp[f][j]); } if(k[i]< arr[i]) { add(ans, mul(k[i], dp[1-f][k[i]])); //printf("ans is now %d\n", ans); } else { add(ans, mul(arr[i]-1, dp[1-f][k[i]])); } } printf("%d\n", ans+1); } }

Compilation message (stderr)

teams.cpp: In function 'int main()':
teams.cpp:28:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf("%d", &n);
                           ^
teams.cpp:31:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i<= n; i++) scanf("%d", &arr[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...