AWC0003 D - 連続練習日数

Difficulty:None

問題

長さNの数列Aがある。次の条件を満たす区間はいくつあるか。

区間の長さがK以上

区間内の和がM以上

解法

尺取り法をすればよい。累積和+二分探索でも解ける。

実装

code:cpp

bool solve(){

LL(n,k,m);

vector<ll>a(n);

cin >> a;

ll ans{},sum{};

ll r{};

rep(l,n){

while(r<n and ((r-l)<k or sum<m)){

r++;

}

deb(l,r);

if(sum>=m and r-l>=k){

ans += n+1-r;

}

}

O(ans);

return false;

}