Submission #371989

#TimeUsernameProblemLanguageResultExecution timeMemory
371989Andyvanh1Calvinball championship (CEOI15_teams)C++14
100 / 100
270 ms768 KiB
#include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> using namespace std; #define vt vector #define INF INT_MAX #define pb push_back typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vt<pair<int,int>> vpii; vt<vi> adjlist; vt<bool> visited; void solve(){ int n, r; cin>>n>>r; adjlist.resize(n); for(int i = 0; i < r; i++){ int u, v; cin>>u>>v; adjlist[u-1].pb(v-1); adjlist[v-1].pb(u-1); } int sz = (1<<n); bool bol1 = false; for(int j = 1; j < sz; j++){ bool arr[n]; for(int i = 0; i < n; i++){ arr[i] = false; } int jj = j; int idn = 0; while(jj!=0){ if(jj%2==1){ arr[idn] = true; } jj/=2; idn++; } vi a; for(int i = 0; i < n; i++){ if(arr[i]){ a.pb(i); } } if(a.size()<=3){ continue; } bool bol = true; for(auto& e:a){ int ct = 0; for(auto& ee: adjlist[e]){ if(arr[ee]){ ct++; } } if(ct!=2){ bol = false; break; } } if(bol){ visited.resize(n); for(int i = 0; i < n; i++){ visited[i] = false; } vi b; stack<int> stk; stk.push(a[0]); visited[a[0]] = true; while(!stk.empty()){ int node = stk.top(); stk.pop(); b.pb(node); for(auto&e : adjlist[node]){ if(arr[e]&&!visited[e]){ stk.push(e); visited[e] = true; } } } for(auto& e: b){ cout<<e+1<<" "; } bol1 = true; break; } } if(!bol1){ cout<<"no"; } } void solve2(){ int n; cin>>n; stack<pair<int,int>> q; vi arr(n); for(int i = 0; i < n; i++){ cin>>arr[i]; } int Max = 1; for(int i = 1; i < n; i++){ q.push({arr[i]-1,Max}); Max = max(Max,arr[i]); } ll dp1[n+1][2]; for(int i = 1; i <= n; i++){ dp1[i][0] = 1; } ll ans = 0; int x = 0; while(!q.empty()){ auto& e = q.top(); q.pop(); ans+=(ll)e.first*dp1[e.second][x]; ans%=1000007; x = 1-x; for(int i = 1; i <= n; i++){ dp1[i][x] = (ll)i*dp1[i][1-x]+dp1[i+1][1-x]; dp1[i][x]%=1000007; } } cout<<(ans+1)%1000007; } int main() { solve2(); return 0; }
#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...