Submission #116747

#TimeUsernameProblemLanguageResultExecution timeMemory
116747JohnTitorCalvinball championship (CEOI15_teams)C++11
100 / 100
926 ms632 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "Calvinball" int n; const ll base=1000007; ll f[10002]; ll g[10002]; int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); FOR(i, 1, n) f[i]=1; FOR(i, 1, n){ FOR(j, 0, n) f[j]=(f[j]*j+f[j+1])%base; g[i]=f[0]; } int team=0, a; ll ans=1; FOR(i, 1, n){ ll oldj=f[0]; FOR(j, 1, n){ ll temp=f[j]; f[j]=(oldj-f[j-1]*(j-1))%base; oldj=temp; } f[0]=g[n-i]; read(a); ans+=(a-1)*f[team]; team=max(team, a); } ans%=base; if(ans<0) ans+=base; writeln(ans); } //f[i][j] -> have i more people and now have j team ///f[i][j]=f[i-1][j]*j+f[i-1][j+1]; ///f[i+1][j]=f[i][j]*j+f[i][j+1]; ///f[i+1][j-1]=f[i][j-1]*(j-1)+f[i][j]; ///f[i][j]=f[i+1][j-1]-f[i][j-1]*(j-1);
#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...