yukicoder No.973 - 余興

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20200119-1）のコード

C++に変換後のコードはこちら

int N, X, A[5000];

int lf[5000], rg[5000];
fenwick<int> dp1[5000];
fenwick<int> dp2[5000];

{
  int i, j, k, len, ok;
  rd(N,X,A(N));

  rep(i,N){
    j = i; k = A[i];
    while(j-1 >= 0 && k + A[j-1] <= X) k += A[--j];
    lf[i] = j;

    j = i; k = A[i];
    while(j+1 < N  && k + A[j+1] <= X) k += A[++j];
    rg[i] = j;
  }

  rep(i,N) dp1[i].malloc(N), dp1[i].init(N);
  rep(i,N) dp2[i].malloc(N), dp2[i].init(N);

  rep(len,1,N+1) rep(i,N-len+1){
    j = i + len - 1;
    ok = 0;
    if(len > 1 && dp1[i].range(max(i,lf[j]-1), j-1)) ok++;
    if(len > 1 && dp2[j].range(i+1,min(j,rg[i]+1))) ok++;
    if(ok==0) dp1[i].add(j,1), dp2[j].add(i,1);
  }
  k = dp1[0].range(N-1,N-1);
  wt(if[k,"B","A"]);
}

Current time: 2024年04月26日19時28分04秒
Last modified: 2020年01月19日05時34分08秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)