Submission #118749

#TimeUsernameProblemLanguageResultExecution timeMemory
118749silxikysCalvinball championship (CEOI15_teams)C++14
20 / 100
227 ms1536 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn = 1e4+4, M = 1e9+7; int n, a[maxn]; int dp[2][maxn]; void madd(int& a, int b) { a = (a+b) % M; } int mult(int a, int b) { return (1LL*a*b) % M; } struct Node { int s, e, m; //covers s,e; int sum; int maxi; Node *l, *r; Node(int a, int b) { s = a; e = b; sum = 0; maxi = 0; if (s != e) { m = (s+e)/2; l = new Node(s,m); r = new Node(m+1,e); } else { l = NULL; r = NULL; } } void add(int i, int x) { if (s == e) { sum += x; maxi = sum; return; } if (i <= m) { l->add(i,x); } else if (i > m) { r->add(i,x); } else assert(false); sum = l->sum + r->sum; maxi = max(l->maxi,r->maxi); } int getmaxi(int st, int en) { if (st <= s && e <= en) { return maxi; } int ret = 0; if (st <= m) { ret = max(ret,l->getmaxi(st,en)); } if (en > m) { ret = max(ret,r->getmaxi(st,en)); } return ret; } int getsum(int st, int en) { if (st <= s && e <= en) { return sum; } int ret = 0; if (st <= m) { ret += l->getsum(st,en); } if (en > m) { ret += r->getsum(st,en); } return ret; } }; int br = 0; void DFS(vector<int> v) { if (v.size() == n) { bool poss = true; int biggestSeen = 0; for (int i: v) { if (i > biggestSeen+1) { poss = false; break; } biggestSeen = max(biggestSeen,i); } if (poss) { br++; /* for (int i: v) { cout << i << ' '; } cout << '\n'; */ } } else { for (int j = 1; j <= n; j++) { v.push_back(j); DFS(v); v.pop_back(); } } } int brute() { vector<int> v; DFS(v); return br; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; Node *root = new Node(0,n); for (int i = 1; i <= n; i++) { cin >> a[i]; root->add(i,a[i]); } for (int i = 1; i <= n+1; i++) { dp[0][i] = 1; } int ans = 0; for (int i = n; i >= 1; i--) { for (int j = 1; j <= i; j++) { dp[1][j] = (mult(j,dp[0][j]) + dp[0][j+1]) % M; //cout << dp[0][j] << ' '; } //cout << '\n'; int m = root->getmaxi(0,i-1); if (m < a[i]) { madd(ans,mult(m,dp[0][m])); } else { madd(ans,mult(a[i]-1,dp[0][m])); } //cout << i << ": " << mult(a[i]-1,dp[0][m]) << '\n'; for (int j = 1; j <= n; j++) { dp[0][j] = dp[1][j]; } } cout << ((ans+1)%M) << '\n'; //cout << "brute : " << brute() << '\n'; }

Compilation message (stderr)

teams.cpp: In function 'void DFS(std::vector<int>)':
teams.cpp:88:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (v.size() == n) {
         ~~~~~~~~~^~~~
#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...