Codeforces Round #587 DIV3 F問題 - Wi-Fi

Source

Codeforces Round #587 DIV3 F問題
Problem description

問題概要

省略

解法

省略

cLay（version 20190925-1）のコード

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

//no-unlocked
int N, K;
char S[200002];
ll dp[200002];
{
  int i, j;
  ll tmp;
  segtree_Point_Minval<ll> t;
  rd(N,K,S);
  rep(i,N) S[i] -= '0';

  rep(i,N) dp[i+1] = ll_inf;
  
  t.malloc(N+1);
  t.setN(N+1);
  rep(i,N+1) t[i] = dp[i];
  t.build();

  rep(i,N){
    if(dp[i+1] > dp[i] + i + 1){
      dp[i+1] = dp[i] + i + 1;
      t.change(i+1, dp[i+1]);
    }
    if(S[i]){
      tmp = t.getMinVal(max(0,i-K), N) + i + 1;
      j = min(N, i+1+K);
      if(dp[j] > tmp){
        dp[j] = tmp;
        t.change(j, tmp);
      }
    }
  }

  wt(dp[N]);
}

Current time: 2024年04月20日16時33分32秒
Last modified: 2019年09月26日01時48分16秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF587 CF_Div3_F
トップページに戻る

Logged in as: unknown user (not login)