BOJ 25916 - 싫은데요

image.png

전형적인 투 포인터 문제로, $M$ 길이까지 계속 $L, R$을 업데이트 해가며 가장 가장 구간합이 큰 구간의 구간합이 정답이다.

void solve() {
   int n, m;
   cin >> n >> m;
   vi a(n);
   fv(a);
   int ans = 0;
   for (int l = 0, r = 0, s = 0; l < n; l++) {
      while (r < n && s + a[r] <= m)s += a[r], r++;
      ans = max(ans, s);
      s -= a[l];
   }
   cout << ans;
}

Tags:

Categories:

Updated:

Comments