Submission #2367885
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
const int mod=1000000007;
inline void add(int &a,int b){
a+=b;
if(a>=mod)a-=mod;
}
int mpow(int n,int m){
int ret=1;
while(m){
if(m&1)ret=ret*n%mod;
n=n*n%mod;
m>>=1;
}
return ret;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
fact_exec(){
fact[0]=1;
for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
}factexec;
int nCk(int n,int k){
if(n<0|k<0||k>n)return 0;
return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
if(n<0||k<0||k>n)return 0;
return fact[n]*inv[n-k]%mod;
}
int N;
int dp[2][52][52][52][52];
int sum[52][52][52][52];
int sum2[52][52][52][52];
int sum3[52][52][52];
int sum4[52][52][52];
signed main(){
cin>>N;
vint A(2*N-1);
rep(i,2*N-1)cin>>A[i];
sort(all(A));
while(N>1&&A[N-2]==A[N-1]&&A[N-1]==A[N]){
A.erase(A.begin()+N-2,A.begin()+N);
N--;
}
if(N>1&&A[N-2]==A[N-1])dp[0][N-1][N][N-1][0]=1;
else if(N>1&&A[N-1]==A[N])dp[0][N-1][0][N-1][N]=1;
else dp[0][N-1][0][N-1][0]=1;
for(int x=0;x<N-1;x++){
memset(sum,0,sizeof(sum));
memset(sum2,0,sizeof(sum2));
memset(sum3,0,sizeof(sum3));
memset(sum4,0,sizeof(sum4));
for(int i=0;i<N;i++){
for(int j=0;j<=N;j++){
for(int k=0;k<N;k++){
for(int l=0;l<=N;l++){
if(dp[x&1][i][j][k][l]==0)continue;
if(j==N||l==N){
int jj=j,ll=l;
if(jj==N)jj=0;
if(ll==N)ll=0;
int a=max(N-1-x-1,k);
int b=k+ll;
if(a<b){
add(sum[i][jj][k][a-k],dp[x&1][i][j][k][l]);
add(sum[i][jj][k][b-k],mod-dp[x&1][i][j][k][l]);
}
a=N-1-x-1;
if(a<k){
add(dp[(x+1)&1][i][jj][a][(a>0&&A[2*N-1-1-a]==A[2*N-1-1-(a-1)])*N],dp[x&1][i][j][k][l]);
}
a=N-1-x-1+1;
b=k;
if(a<b){
add(sum3[i][jj][a],dp[x&1][i][j][k][l]);
add(sum3[i][jj][b],mod-dp[x&1][i][j][k][l]);
}
/*
for(int m=N-1-x-1;m<k+ll;m++){
if(m>=k)add(dp[(x+1)&1][i][jj][k][m-k],dp[x&1][i][j][k][l]);
else if(m==N-1-x-1||A[2*N-1-1-m]!=A[2*N-1-1-(m-1)])add(dp[(x+1)&1][i][jj][m][(m>0&&A[2*N-1-1-m]==A[2*N-1-1-(m-1)])*N],dp[x&1][i][j][k][l]);
}
*/
a=max(N-1-x-1,i);
b=i+jj;
if(a<b){
add(sum2[i][a-i][k][ll],dp[x&1][i][j][k][l]);
add(sum2[i][b-i][k][ll],mod-dp[x&1][i][j][k][l]);
}
a=N-1-x-1;
if(a<i){
add(dp[(x+1)&1][a][(a>0&&A[a]==A[a-1])*N][k][ll],dp[x&1][i][j][k][l]);
}
a=N-1-x-1+1;
b=i;
if(a<b){
add(sum4[a][k][ll],dp[x&1][i][j][k][l]);
add(sum4[b][k][ll],mod-dp[x&1][i][j][k][l]);
}
/*
for(int m=N-1-x-1;m<i+jj;m++){
if(m>=i)add(dp[(x+1)&1][i][m-i][k][ll],dp[x&1][i][j][k][l]);
else if(m==N-1-x-1||A[m]!=A[m-1])add(dp[(x+1)&1][m][(m>0&&A[m]==A[m-1])*N][k][ll],dp[x&1][i][j][k][l]);
}
*/
}
else{
add(dp[(x+1)&1][i][j][k][l],dp[x&1][i][j][k][l]);
int a=max(N-1-x-1,k);
int b=k+l;
if(a<b){
add(sum[i][j+1][k][a-k],dp[x&1][i][j][k][l]);
add(sum[i][j+1][k][b-k],mod-dp[x&1][i][j][k][l]);
}
a=N-1-x-1;
if(a<k){
add(dp[(x+1)&1][i][j+1][a][(a>0&&A[2*N-1-1-a]==A[2*N-1-1-(a-1)])*N],dp[x&1][i][j][k][l]);
}
a=N-1-x-1+1;
b=k;
if(a<b){
add(sum3[i][j+1][a],dp[x&1][i][j][k][l]);
add(sum3[i][j+1][b],mod-dp[x&1][i][j][k][l]);
}
/*
for(int m=N-1-x-1;m<k+l;m++){
if(m>=k);//add(dp[(x+1)&1][i][j+1][k][m-k],dp[x&1][i][j][k][l]);
else if(m==N-1-x-1||A[2*N-1-1-m]!=A[2*N-1-1-(m-1)])add(dp[(x+1)&1][i][j+1][m][(m>0&&A[2*N-1-1-m]==A[2*N-1-1-m+1])*N],dp[x&1][i][j][k][l]);
}*/
a=max(N-1-x-1,i);
b=i+j;
if(a<b){
add(sum2[i][a-i][k][l+1],dp[x&1][i][j][k][l]);
add(sum2[i][b-i][k][l+1],mod-dp[x&1][i][j][k][l]);
}
a=N-1-x-1;
if(a<i){
add(dp[(x+1)&1][a][(a>0&&A[a]==A[a-1])*N][k][l+1],dp[x&1][i][j][k][l]);
}
a=N-1-x-1+1;
b=i;
if(a<b){
add(sum4[a][k][l+1],dp[x&1][i][j][k][l]);
add(sum4[b][k][l+1],mod-dp[x&1][i][j][k][l]);
}
/*
for(int m=N-1-x-1;m<i+j;m++){
if(m>=i);//add(dp[(x+1)&1][i][m-i][k][l+1],dp[x&1][i][j][k][l]);
else if(m==N-1-x-1||A[m]!=A[m-1])add(dp[(x+1)&1][m][(m>0&&A[m]==A[m-1])*N][k][l+1],dp[x&1][i][j][k][l]);
}
*/
}
dp[x&1][i][j][k][l]=0;
}
}
}
}
rep(i,N)rep(j,x+2)rep(k,N)rep(l,x+2){
add(sum[i][j][k][l+1],sum[i][j][k][l]);
add(dp[(x+1)&1][i][j][k][l],sum[i][j][k][l]);
add(sum2[i][j+1][k][l],sum2[i][j][k][l]);
add(dp[(x+1)&1][i][j][k][l],sum2[i][j][k][l]);
}
rep(i,N)rep(j,N+1)rep(k,N){
add(sum3[i][j][k+1],sum3[i][j][k]);
if(k&&A[2*N-1-1-k]!=A[2*N-1-1-(k-1)])add(dp[(x+1)&1][i][j][k][0],sum3[i][j][k]);
}
rep(i,N)rep(k,N)rep(l,N+1){
add(sum4[i+1][k][l],sum4[i][k][l]);
if(i&&A[i]!=A[i-1])add(dp[(x+1)&1][i][0][k][l],sum4[i][k][l]);
}
}
/*
for(int x=0;x<N-1;x++){
for(int i=2*N-1;i>=0;i--){
int j=N-1-x;
for(int k=2*N-1;k>=0;k--){
int l=N-1-x;
add(dp[x+1][i][k],dp[x][i][k]);
for(int m=l-1;m<k;m++)add(dp[x+1][i+1][m],dp[x][i][k]);
for(int m=j-1;m<i;m++)add(dp[x+1][m][k+1],dp[x][i][k]);
}
}
}*/
int ans=0;
rep(i,N+1)rep(j,N+1)rep(k,N+1)rep(l,N+1)add(ans,dp[(N-1)&1][i][j][k][l]);
cout<<ans<<endl;
return 0;
}
Submission Info
| Submission Time |
|
| Task |
F - Prefix Median |
| User |
latte0119 |
| Language |
C++14 (GCC 5.4.1) |
| Score |
2000 |
| Code Size |
8718 Byte |
| Status |
AC |
| Exec Time |
1719 ms |
| Memory |
124288 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 |
28 ms |
71040 KB |
| 00_example_02.txt |
AC |
42 ms |
75136 KB |
| 00_example_03.txt |
AC |
123 ms |
87424 KB |
| 01.txt |
AC |
1719 ms |
124288 KB |
| 02.txt |
AC |
1241 ms |
120192 KB |
| 03.txt |
AC |
307 ms |
103808 KB |
| 04.txt |
AC |
203 ms |
95616 KB |
| 05.txt |
AC |
160 ms |
91520 KB |
| 06.txt |
AC |
638 ms |
112000 KB |
| 07.txt |
AC |
1718 ms |
124288 KB |
| 08.txt |
AC |
160 ms |
91520 KB |
| 09.txt |
AC |
1714 ms |
124288 KB |
| 10.txt |
AC |
56 ms |
75136 KB |
| 11.txt |
AC |
92 ms |
83328 KB |
| 12.txt |
AC |
140 ms |
87424 KB |
| 13.txt |
AC |
493 ms |
107904 KB |
| 14.txt |
AC |
822 ms |
116096 KB |
| 15.txt |
AC |
56 ms |
75136 KB |
| 16.txt |
AC |
1585 ms |
124288 KB |
| 17.txt |
AC |
100 ms |
83328 KB |
| 18.txt |
AC |
28 ms |
71040 KB |
| 19.txt |
AC |
13 ms |
11648 KB |
| 20.txt |
AC |
114 ms |
83328 KB |
| 21.txt |
AC |
107 ms |
83328 KB |
| 22.txt |
AC |
49 ms |
75136 KB |
| 23.txt |
AC |
275 ms |
99712 KB |
| 24.txt |
AC |
148 ms |
91520 KB |
| 25.txt |
AC |
260 ms |
99712 KB |
| 26.txt |
AC |
323 ms |
103808 KB |
| 27.txt |
AC |
139 ms |
87424 KB |
| 28.txt |
AC |
1355 ms |
124288 KB |
| 29.txt |
AC |
189 ms |
95616 KB |
| 30.txt |
AC |
319 ms |
103808 KB |
| 31.txt |
AC |
42 ms |
75136 KB |
| 32.txt |
AC |
297 ms |
103808 KB |
| 33.txt |
AC |
43 ms |
75136 KB |
| 34.txt |
AC |
245 ms |
99712 KB |
| 35.txt |
AC |
1121 ms |
120192 KB |
| 36.txt |
AC |
28 ms |
71040 KB |
| 37.txt |
AC |
1152 ms |
120192 KB |
| 38.txt |
AC |
300 ms |
103808 KB |
| 39.txt |
AC |
204 ms |
95616 KB |
| 40.txt |
AC |
158 ms |
91520 KB |
| 41.txt |
AC |
597 ms |
112000 KB |
| 42.txt |
AC |
1584 ms |
124288 KB |
| 43.txt |
AC |
158 ms |
91520 KB |
| 44.txt |
AC |
1594 ms |
124288 KB |
| 45.txt |
AC |
56 ms |
75136 KB |
| 46.txt |
AC |
85 ms |
79232 KB |
| 47.txt |
AC |
139 ms |
87424 KB |
| 48.txt |
AC |
471 ms |
107904 KB |
| 49.txt |
AC |
775 ms |
116096 KB |
| 50.txt |
AC |
56 ms |
75136 KB |
| 51.txt |
AC |
13 ms |
11648 KB |