Created
May 27, 2020 08:08
-
-
Save gbrls/72cfcfd9895658d08b3fd11ca0928640 to your computer and use it in GitHub Desktop.
Solução da OBI 2019 f2 soma
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#define int long long int | |
using namespace std; | |
const int M = 5e5+20; | |
int n,s; | |
int32_t main() { | |
cin>>n>>s; | |
int ans=0; | |
vector<int> vec(n); | |
for(int i=0;i<n;i++) cin>>vec[i]; | |
for(int i=1;i<n;i++) vec[i] += vec[i-1]; | |
for(int i=0;i<n;i++) cout<<vec[i]<<(i==n-1?'\n':' '); | |
for(int i=0;i<n;i++) { | |
if(vec[i]==s) ans++; | |
} | |
for(int i=0;i<n;i++) { | |
int c = vec[i]; | |
int tar = c + s; | |
auto a = lower_bound(vec.begin()+i+1,vec.end(),tar); | |
auto b = upper_bound(vec.begin()+i+1,vec.end(),tar); | |
if(*a == tar) { | |
ans += b-a; | |
} | |
} | |
cout<<ans<<'\n'; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment