Ý tưởng

Nếu bạn không hiểu, bạn có thể hỏi thêm

Ta gọi pf[i] là tổng các phần tử từ a[1] đến a[i] (để tiện thì ta gọi thêm pf[0] = 0)

Ta thấy, để một dãy a[i...j] (i < j, tính cả a[i] và a[j]) đẹp thì pf[j] - pf[i-1] = k.

Ý tưởng của bài này là với mỗi pf[j], ta tìm xem có bao nhiêu pf[i] với 0 <= i < j sao cho pf[j] - pf[i] = k

Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    unordered_map<int,int> mp;
    int n,k; cin >> n >> k;
    int a[n+1];
    int current_sum = 0, ans = 0;
    mp[0] = 1; // vi pf[0] = 0
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        current_sum += a[i];
        ans += mp[current_sum - k];
        mp[current_sum]++;
    }
    cout << ans;
    return 0;
}