fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int maximum(vector<int>&v,int k){
  4.     int sum=0;
  5.     int ans=0;
  6.     unordered_map<int,int>m;
  7.     for(int i=0;i<v.size();i++){
  8.         sum+=v[i];
  9.         if(m.find(sum-k)!=m.end()){
  10.             ans=max(ans,i-m[sum-k]);
  11.         }
  12.         if(sum==k){
  13.             ans=max(ans,i+1);
  14.         }
  15.         if(m.find(sum)==m.end()){
  16.             m[sum]=i;
  17.         }
  18.  
  19.     }
  20.     return ans;
  21. }
  22. int minimum(vector<int>&v,int k){
  23.     int sum=0;
  24.     int ans=INT_MAX;
  25.     unordered_map<int,int>m;
  26.     for(int i=0;i<v.size();i++){
  27.         sum+=v[i];
  28.         if(m.find(sum-k)!=m.end()){
  29.             ans=min(ans,i-m[sum-k]);
  30.         }
  31.         if(sum==k){
  32.             ans=min(ans,i+1);
  33.         }
  34.  
  35.             m[sum]=i;
  36.  
  37.  
  38.     }
  39.     return ans;
  40. }
  41. int count(int s,vector<int>&v,int k){
  42.     if(s<1 ||s>v.size())return 0;
  43.     int ans=0;
  44.     int sum=0;
  45.     int j=s-1;
  46.     int i=0;
  47.     for(int a=j;a>=i;a--)sum+=v[a];
  48.     while(j<v.size()){
  49.         if(sum==k)ans++;
  50.         j++;
  51.         sum-=v[i];
  52.         if(j<v.size())sum+=v[j];
  53.         i++;
  54.     }
  55.     return ans;
  56. }
  57.  
  58. int main(){
  59. 	int n;cin>>n;
  60. 	int k;cin>>k;
  61. 	vector<int>v(n);
  62. 	for(int i=0;i<n;i++)cin>>v[i];
  63. 	cout<<"Max Count:"<<count(maximum(v,k),v,k)<<endl;
  64.     cout<<"Min Count:"<<count(minimum(v,k),v,k)<<endl;
  65. 	return 0;
  66. }
  67.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6
6
3 1 2 1 3 6
stdout
copy 
Max Count:2
Min Count:1
https://ideone.com/jU1Xtr
language:
C++14 (gcc 8.3)
created:
16 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!