AtCoder Regular Contest 108
問題文
省略
省略
C++に変換後のコードはこちら
int N, A[2002];
int v[2002], ind[2002];
Modint dp[2002][2002];
fenwick<Modint> d1[2002], d2[2002];
fenwick<int> d[2002];
{
int i, j, t;
rd(N,A(N));
arrInsert(0, N, A, 0);
arrInsert(N, N, A, N);
rep(i,N) d[i].malloc(N,1);
rep(i,N) d1[i].malloc(N,1);
rep(i,N) d2[i].malloc(N,1);
rep(i,N) (v[i], ind[i]) = (A[i], i);
sortA(N, v, ind);
rep(len,1,N) rep(ii,N-len){
(i, j) = (ind[ii], ind[ii+len]);
if(i >= j || A[i] > A[j]) continue;
t = d[i].range(i,j);
if(t){
dp[i][j] += d1[i].range(i,j);
dp[i][j] += d2[j].range(i,j);
dp[i][j] /= t;
dp[i][j] += 1;
}
d[i].add(j, 1);
d1[i].add(j, dp[i][j]);
d2[j].add(i, dp[i][j]);
}
wt(dp[0][N-1]);
}
Current time: 2024年03月29日19時24分01秒
Last modified: 2020年11月22日17時04分37秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Regular_Contest ARC108 ARC_E
トップページに戻る
Logged in as: unknown user (not login)