Guest User

Untitled

a guest
Feb 18th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.74 KB | None | 0 0
  1. //
  2. // Created by fpdjsns
  3. // Copyright © 2019 fpdjsns. All rights reserved.
  4. //
  5.  
  6. /*
  7. * 시간복잡도 : O(N)
  8. * 공간복잡도 : O(N)
  9. */
  10. #include<iostream>
  11. #include<vector>
  12.  
  13. using namespace std;
  14.  
  15. int main() {
  16.  
  17. int N, M;
  18. cin >> N >> M;
  19. vector<int> subSum(N + 1, 0);
  20. int tmp;
  21. for (int i = 1; i <= N; i++){
  22. cin >> tmp;
  23. subSum[i] = subSum[i - 1] + tmp;
  24. }
  25. int ans = 0;
  26. int l = 0, r = 1;
  27. while (l <= N && r <= N) {
  28. int sum = subSum[r] - subSum[l];
  29. if (sum == M) {
  30. int cnt = 1;
  31. while (r + 1 <= N && subSum[r] == subSum[r + 1]) {
  32. cnt++; r++;
  33. }
  34. while (l + 1 <= N && subSum[l] == subSum[l +1]) {
  35. cnt++; l++;
  36. }
  37. l++; r++;
  38. ans += cnt;
  39. }
  40. else if(sum < M){
  41. r++;
  42. }
  43. else {
  44. l++;
  45. }
  46. }
  47. cout << ans;
  48.  
  49. return 0;
  50. }
Add Comment
Please, Sign In to add comment