fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.     int n,k;
  7.     cin>>n>>k;
  8.  
  9.     int a[n];
  10.  
  11.     for(int i=0; i<n; i++)
  12.     {
  13.         cin>>a[i];
  14.     }
  15.  
  16.     int preSum[n+1]= {0};
  17.  
  18.     for(int i=1; i<=n; i++)
  19.     {
  20.         preSum[i] = preSum[i-1]+ a[i-1];  // 0 3 3 4 7 5 7    // instead of prefix sum array we can get this by just maintaining a currSum var
  21.     }
  22.  
  23.     int curSum=0;
  24.  
  25.     unordered_map<int,int>mp;
  26.     int maxlen=0, minlen= n+1;
  27.  
  28.     mp[0]=0;
  29.  
  30.     // for(int i=0; i<n; i++)
  31.     // {
  32.     // 	curSum+= a[i];
  33.  
  34.     // 	if(mp.find(curSum-k)!= mp.end())
  35.     // 	{
  36.     // 		maxlen= max(maxlen, i- mp[curSum-k] +1 );
  37.     // 	}
  38.  
  39.     // 	if(mp.find(curSum)==mp.end())
  40.     // 	{
  41.     // 		mp[curSum]= i;
  42.     // 	}
  43.     // }
  44.  
  45.  
  46.     for(int i=1; i<=n; i++)
  47.     {
  48.         if(mp.find(preSum[i]-k)!=mp.end())
  49.         {
  50.  
  51.  
  52.             maxlen = max(maxlen,(i-mp[preSum[i]-k]));
  53.  
  54.         }
  55.  
  56.         if(mp.find(preSum[i])==mp.end())
  57.         {
  58.              mp[preSum[i]]= i;
  59.         }
  60.  
  61.     }
  62.  
  63.     cout<<maxlen <<endl;
  64.  
  65.  
  66.  
  67.  
  68. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/gSiM2d
5 0
0 0 0 0 0
language:
C++14 (gcc 8.3)
created:
4 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!