ABC130-D. Enough Array

https://atcoder.jp/contests/abc130/tasks/abc130_d

  • 어디선가 많이 풀어본 배열문제
  • 빠르게 Two-Point 해법을 생각해냄, 시간 공간 모두 선형.
  • 다만 입력 자체가 long long 범위인걸 못보고 있다고 WA맞음.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N = 0, K = 0, sum = 0, right = 0, ans = 0;
  vector<long long> arr;
  ios::sync_with_stdio(false);
  cin >> N >> K;
  arr.resize(N);
  for(long long i = 0; i < N; i++)
    cin >> arr[i];
  for(long long left = 0; left < N; left++) {
    while(sum < K && right < N)
      sum += arr[right++];
    ans += N - right + (sum >= K);
    sum -= arr[left];
  }
  cout << ans;
}