C. Ski Resort

어떤 qq 이상의 aia_i 가 없는 연속된 구간의 길이를 LL 이라고 한다면

L≥KL \ge K 라면 이 구간에서 가능한 개수는 ∑i=1L−K+1i=(L−K+1)(L−K+2)2\displaystyle \sum_{i=1}^{L-K+1}i=\dfrac{(L-K+1)(L-K+2)}{2} 이다.

이걸 정답에 모두 더해주면 된다.

void solve() {  
   int n, k, q;  
   cin >> n >> k >> q;  
   vi a(n);  
   fv(a);  
   vi idx(n);  
   idx.pb(-1);  
   for (int i = 0; i < n; i++) if (a[i] > q) idx.pb(i);  
   idx.pb(n);  
  
   int ans = 0;  
   for (int i = 1; i < sz(idx); i++) {  
      int len = idx[i] - idx[i - 1] - 1;  
      if (len >= k) {  
         ans += (len - k + 1) * (len - k + 2) / 2;  
      }  
   }  
   cout << ans << endl;  
}

Comments

You may also enjoy