Submission #1200688
Source Code Expand
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} template<unsigned int mod_> struct ModInt{ using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr static uint mod = mod_; uint v; ModInt():v(0){} ModInt(ll v):v(normS(v%mod+mod)){} explicit operator bool() const {return v!=0;} static uint normS(const uint &x){return (x<mod)?x:x-mod;} // [0 , 2*mod-1] -> [0 , mod-1] static ModInt make(const uint &x){ModInt m; m.v=x; return m;} ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));} ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));} ModInt operator-() const { return make(normS(mod-v)); } ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);} ModInt operator/(const ModInt& b) const { return *this*b.inv();} ModInt& operator+=(const ModInt& b){ return *this=*this+b;} ModInt& operator-=(const ModInt& b){ return *this=*this-b;} ModInt& operator*=(const ModInt& b){ return *this=*this*b;} ModInt& operator/=(const ModInt& b){ return *this=*this/b;} ll extgcd(ll a,ll b,ll &x,ll &y) const{ ll u[]={a,1,0},v[]={b,0,1}; while(*v){ ll t=*u/ *v; rep(i,3) swap(u[i]-=t*v[i],v[i]); } if(u[0]<0) rep(i,3) u[i]=-u[i]; x=u[1],y=u[2]; return u[0]; } ModInt inv() const{ ll x,y; extgcd(v,mod,x,y); return make(normS(x+mod)); } bool operator==(const ModInt& b) const { return v==b.v;} bool operator!=(const ModInt& b) const { return v!=b.v;} friend istream& operator>>(istream &o,ModInt& x){ ll tmp; o>>tmp; x=ModInt(tmp); return o; } friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;} }; using mint = ModInt<1000000007>; int N; int L; int a[99]; void input(){ cin>>N; L=2*N-1; rep(i,L) cin>>a[i]; sort(a,a+L); } mint dp[50][110][110]; int main(){ input(); dp[0][0][0]=1; int mid=N-1; rep(t,N-1){ int loff=(a[mid-t]!=a[mid-t-1]); int roff=(a[mid+t]!=a[mid+t+1]); rep(l_,110) rep(r_,110) if(dp[t][l_][r_]){ mint& val=dp[t][l_][r_]; int l=l_+loff, r=r_+roff; //stay dp[t+1][l][r]+=val; //left rep(x,l) dp[t+1][l-1-x][r+1]+=val; //right rep(x,r) dp[t+1][l+1][r-1-x]+=val; } } mint ans=0; rep(i,110) rep(j,110) ans+=dp[N-1][i][j]; cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Prefix Median |
User | sigma425 |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 2907 Byte |
Status | AC |
Exec Time | 10 ms |
Memory | 2560 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 2000 / 2000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 2 ms | 2560 KB |
00_example_02.txt | AC | 2 ms | 2560 KB |
00_example_03.txt | AC | 3 ms | 2560 KB |
01.txt | AC | 10 ms | 2560 KB |
02.txt | AC | 8 ms | 2560 KB |
03.txt | AC | 4 ms | 2560 KB |
04.txt | AC | 3 ms | 2560 KB |
05.txt | AC | 3 ms | 2560 KB |
06.txt | AC | 5 ms | 2560 KB |
07.txt | AC | 10 ms | 2560 KB |
08.txt | AC | 3 ms | 2560 KB |
09.txt | AC | 10 ms | 2560 KB |
10.txt | AC | 2 ms | 2560 KB |
11.txt | AC | 3 ms | 2560 KB |
12.txt | AC | 3 ms | 2560 KB |
13.txt | AC | 5 ms | 2560 KB |
14.txt | AC | 6 ms | 2560 KB |
15.txt | AC | 2 ms | 2560 KB |
16.txt | AC | 5 ms | 2560 KB |
17.txt | AC | 3 ms | 2560 KB |
18.txt | AC | 2 ms | 2560 KB |
19.txt | AC | 2 ms | 2560 KB |
20.txt | AC | 3 ms | 2560 KB |
21.txt | AC | 3 ms | 2560 KB |
22.txt | AC | 2 ms | 2560 KB |
23.txt | AC | 3 ms | 2560 KB |
24.txt | AC | 3 ms | 2560 KB |
25.txt | AC | 3 ms | 2560 KB |
26.txt | AC | 3 ms | 2560 KB |
27.txt | AC | 3 ms | 2560 KB |
28.txt | AC | 5 ms | 2560 KB |
29.txt | AC | 3 ms | 2560 KB |
30.txt | AC | 3 ms | 2560 KB |
31.txt | AC | 2 ms | 2560 KB |
32.txt | AC | 3 ms | 2560 KB |
33.txt | AC | 2 ms | 2560 KB |
34.txt | AC | 3 ms | 2560 KB |
35.txt | AC | 4 ms | 2560 KB |
36.txt | AC | 2 ms | 2560 KB |
37.txt | AC | 4 ms | 2560 KB |
38.txt | AC | 3 ms | 2560 KB |
39.txt | AC | 3 ms | 2560 KB |
40.txt | AC | 3 ms | 2560 KB |
41.txt | AC | 4 ms | 2560 KB |
42.txt | AC | 5 ms | 2560 KB |
43.txt | AC | 3 ms | 2560 KB |
44.txt | AC | 5 ms | 2560 KB |
45.txt | AC | 3 ms | 2560 KB |
46.txt | AC | 3 ms | 2560 KB |
47.txt | AC | 3 ms | 2560 KB |
48.txt | AC | 4 ms | 2560 KB |
49.txt | AC | 4 ms | 2560 KB |
50.txt | AC | 3 ms | 2560 KB |
51.txt | AC | 3 ms | 2560 KB |