BOJ 21982 - 상자 빌리기

BOJ 21982 - 상자 빌리기

그냥 일정한 구간의 가장 큰거 두개를 골라서 푸는 문제이다.

최소값 찾기랑 동일한 문제로, 덱으로 풀면 된다.

void solve() {
   int n, X, hs, ha, hb, hc, ws, wa, wb, wc;
   cin >> n >> X >> hs >> ha >> hb >> hc >> ws >> wa >> wb >> wc;

   vi h(n), w(n);
   h[0] = (hs % hc) + 1;
   w[0] = (ws % wc) + 1;

   for (int i = 1; i < n; i++) {
      h[i] = h[i - 1] + 1 + ((h[i - 1] * ha + hb) % hc);
      w[i] = (w[i - 1] * wa + wb) % wc + 1;
   }
   deque<int> dq;
   dq.pb(0);
   int ans = -1;
   for (int i = 1; i < n; i++) {
      while (sz(dq) && h[i] - h[dq[0]] > X) dq.pop_front();
      if (sz(dq)) maxa(ans, w[i] * h[i] + w[dq[0]] * h[dq[0]]);
      while (sz(dq) && w[dq.back()] * h[dq.back()] <= w[i] * h[i]) dq.pop_back();
      dq.push_back(i);
   }
   cout << ans << endl;
}