Submission #38183

#TimeUsernameProblemLanguageResultExecution timeMemory
38183farmersriceCalvinball championship (CEOI15_teams)C++14
70 / 100
109 ms2332 KiB
#include <bits/stdc++.h> //#pragma GCC optimize ("O3") //#pragma GCC target ("sse4") #pragma GCC target ("avx,tune=native") //Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside. AVX is better slightly /* TASK: hidden LANG: C++11 */ using namespace std; typedef long long ll; typedef pair<int, int> pair2; typedef pair<int, pair<int, int> > pair3; typedef pair<int, pair<int, pair<int, int> > > pair4; #define MAXN 10013 #define INF 1000000000000000000LL #define mp make_pair #define add push_back #define remove pop #define MOD 1000007 int n; int values[MAXN]; int num[MAXN]; int dp[2][MAXN]; //dp[i][j]: num ways from point i IF the highest number that appears before us is j (implying value of i is at most j + 1) //dp[i][j] = dp[i + 1][j] * j + dp[i + 1][j + 1] int solve(int index, int first) { if (first < 0 || first > n) return 0; if (first == 0) return dp[index][first] = dp[index ^ 1][first + 1]; ll answer = dp[index ^ 1][first] * first * 1LL + dp[index ^ 1][first + 1]; answer %= MOD * 1LL; return dp[index][first] = (int) answer; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (int i = 0; i < n; i++) { cin >> values[i]; } for (int i = 0; i < 2; i++) { for (int j = 0; j < MAXN; j++) { dp[i][j] = 1; } } int answer = 0; int highestNum = 0; for (int i = 0; i < n; i++) { num[i] = highestNum; highestNum = max(highestNum, values[i]); } int old = 0; for (int i = n - 1; i >= 0; i--) { answer += ((values[i] - 1) * dp[old][num[i]]) % MOD; answer %= MOD; for (int j = 0; j < i; j++) { dp[1 - old][j] = dp[old][j] * j + dp[old][j + 1]; dp[1 - old][j] %= MOD; } old = 1 - old; } /* for (int i = 0; i < n; i++) { //highestNum = max(highestNum, values[i]); //if (highestNum == 1) continue; answer += ((values[i] - 1) * solve(i & 1, highestNum)) % MOD; //cout << "solve " << i << " " << min(values[i] - 2, highestNum - 1) << " is " << solve(i, min(values[i] - 2, highestNum - 1)) << endl; answer %= MOD; highestNum = max(highestNum, values[i]); }*/ cout << answer + 1 << endl; }
#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...