ABC130の「D - Enough Array」

AtCoder Beginner Contest 130のD - Enough Array。

ポイント

ナイーブに実装するとTLEになるので尺取法で計算していく。

コード

typedef long long ll;

int main(int argc, char *argv[]) {
  ll res =0;
  ll n,k;cin>>n>>k;
  std::vector<ll> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  int rp=0;
  ll sum=0;
  for(int lp=0;lp<n;lp++){
    while(sum<k&&rp<n){
      sum += v[rp++];
    }
    if(sum>=k){
      res += n-rp+1;
    }
    sum -= v[lp];
  }
  cout<<res<<endl;

  return 0;
}

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?