B. Heaters

  • Quiz
  • AC
  • 解説
    • editorialがないので書いておく
    • 各ライトが照らせる範囲を[left, right]として持っておき、左のライトから点けるべきか判定していく
    • できるだけライトを点けるのは渋る（ギリギリまで点けない）
    • もしこのライトを点けなければ全てを照らすことはできない時に点ける
    • 範囲を超えた位置に番兵のライトも置いたのが工夫した点
int main(){
    // input
    ll N,r;
    cin>>N>>r;

    VI A(N);
    rep(i, N)cin>>A[i];

    // check
    {
      VI visited(N);
      rep(i,N){
        if(A[i]==1){
          ll left = max(0LL, i-r+1);
          ll right= min(N-1, i+r-1);
          FOR(j, left, right+1){
            visited[j]=1;
          }
        }
      }
      if(SUM(visited)!=N){
        p(-1); return 0;
      }
    }

    vector<PII> V;
    rep(i,N){
      if(A[i]==1){
        ll left = i-r+1;
        ll right = i+r-1;
        V.push_back({left,right});
      }
    }
    V.push_back({2000,3000}); // sentinel

    ll cnt=0;
    ll ri = 0; // ここから塗られていない
    rep(i,SZ(V)){
      if(V[i].first>ri){
        ri = V[i-1].second + 1;
        cnt++;
        if(ri>N-1) break; // 十分塗った
      }
    }
    p(cnt);
    return 0;
}