fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #pragma GCC optimize("O2")
  4. #pragma GCC optimize("O3")
  5. #pragma GCC optimize("Ofast")
  6.  
  7. #define int long long
  8.  
  9. #define pii pair<int,int>
  10. #define ii int,int
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define lb lower_bound
  15. #define ub upper_bound
  16. #define umap unordered_map
  17. #define BIT(mask, i) ((mask >> i)&1)
  18. #define ALL(c) c.begin(), c.end()
  19.  
  20. using namespace std;
  21.  
  22. mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
  23. int rand(int l, int r){
  24.     return  l + rd()*rd()%(r-l+1);
  25. }
  26.  
  27. const int N = 2e5+7; // 2*10^5 + 7
  28. const int M = 1e3+3;
  29. const int MOD = 1e9+7;
  30. const int inf = 3e18;
  31.  
  32. int n, k, a[N], s[N];
  33.  
  34. void cach1(){ // cách đơn giản nhất
  35.     int dem = 0; // đếm số đoạn con có tổng bằng k
  36.     for(int l = 1; l <= n; l++){
  37.         for(int r = l; r <= n; r++){
  38.             long long tong = 0; // lưu tổng của đoạn con từ l->r, 1 <= l <= r <= n
  39.             for(int i = l; i <= r; i++){
  40.                 tong += a[i];
  41.             }
  42.             if(tong == k){ // thỏa mãn tổng = k
  43.                 dem = dem + 1;
  44.             }
  45.         }
  46.     }
  47.     cout << dem << '\n';
  48. }
  49. void cach2(){
  50.     int dem = 0; // đếm số đoạn con có tổng bằng k
  51.     for(int i = 1; i <= n; i++){
  52.         s[i] = s[i-1] + a[i];
  53.     }
  54.     for(int l = 1; l <= n; l++){
  55.         for(int r = l; r <= n; r++){
  56.             long long tong = s[r] - s[l-1];
  57.             if(tong == k){ // thỏa mãn tổng = k
  58.                 dem = dem + 1;
  59.             }
  60.         }
  61.     }
  62.     cout << dem << '\n';
  63. }
  64.  
  65. void cach3(){
  66.     for(int i = 1; i <= n; i++){
  67.         s[i] = s[i-1] + a[i];
  68.     }
  69.     // prefix sum
  70.     map<long long, long long> mp;
  71.     int dem = 0;
  72.     mp[0] = 1;
  73.     for(int i = 1; i <= n; i++){
  74.         dem += mp[s[i] - k]; // đếm số đoạn s[r] - k thỏa mãn s[r] - k == s[l-1]
  75.         mp[s[i]]++; // cộng dồn lên vì sau khi tính được s
  76.     }
  77.     cout << dem;
  78. }
  79.  
  80. signed main(){
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0);
  83.     cout.tie(0);
  84.     cin >> n >> k;
  85.     for(int i = 1; i <= n; i++){
  86.         cin >> a[i];
  87.     }
  88.     cach3();
  89. }
  90.  
  91.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FuPDqy
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!