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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る