BOJ 2694 - 합이 같은 구간

BOJ 2694 - 합이 같은 구간

모든 수의 합 $S$의 약수의 개수가 $\sqrt{S}$ 임을 이용해서 적절히 브루트포스를 돌려줘도 되고, 이분탐색을 써서 하나하나 다음 위치가 가능한지 따져보면서 시간복잡도 커팅을 해서 풀어도 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n), psum(n + 1);
   fv(a);
   for (int i = 0; i < n; i++) psum[i + 1] = psum[i] + a[i];
   vi cand;
   int sum = 0;
   for (int i = 0; i < n; i++) {
      sum += a[i];
      cand.pb(sum);
   }
   debug(cand);
   for (int c: cand) {
      int i = 0, can = 1;
      while (i < n) {
         int l = i, r = n - 1, nxt = -1;
         while (l <= r) {
            int m = l + r >> 1;
            if (psum[m + 1] - psum[i] == c) nxt = m;
            if (psum[m + 1] - psum[i] >= c) {
               r = m - 1;
            } else {
               l = m + 1;
            }
         }
         if (nxt == -1) {
            can = 0;
            break;
         }
         i = nxt + 1;
      }
      if (can) {
         cout << c << endl;
         return;
      }
   }
}