AtCoder Beginner Contest 182 F問題 - Valid payments

Source

AtCoder Beginner Contest 182
問題文

問題概要

省略

解法

省略

cLayversion 20201115-2)のコード

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

int N;
ll X, A[51];

ll lis[51], mem[51][2];
ll solve(int d, int carry){
  ll res = 0;
  if(mem[d][carry] >= 0) return mem[d][carry];

  if(d==N){
    if(carry==0) res++;
  } else {
    if(carry==0){
      res += solve(d+1, 0);
      if(lis[d]) res += solve(d+1, 1);
    } else {
      if((lis[d]+1)*A[d] < A[d+1]) res += solve(d+1, 0);
      res += solve(d+1, 1);
    }
  }
  return mem[d][carry] = res;
}

{
  rd(N,X,A(N));
  A[N] = ll_inf;
  rep(i,N+1) rep(j,2) mem[i][j] = -1;
  rep(i,N) lis[i] = (X%A[i+1])/A[i];
  wt(solve(0,0));
}

Current time: 2021年09月19日21時12分13秒
Last modified: 2020年11月16日22時46分44秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC182 ABC_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン: