Advertisement
Derga

Untitled

Aug 22nd, 2023
677
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. class MinQueue {
  9. private:
  10.     vector<int> data;
  11.     size_t dataBegin;
  12.     vector<int> minData;
  13.     size_t minDataBegin;
  14.  
  15. public:
  16.     void push(int val) {
  17.         data.push_back(val);
  18.         while (minData.size() > minDataBegin && minData.back() > val) {
  19.             minData.pop_back();
  20.         }
  21.         minData.push_back(val);
  22.     }
  23.  
  24.     int min() {
  25.         return minData[minDataBegin];
  26.     }
  27.  
  28.     void pop() {
  29.         if (minData[minDataBegin] == data[dataBegin++]) {
  30.             ++minDataBegin;
  31.         }
  32.     }
  33.  
  34.     void clear() {
  35.         dataBegin = minDataBegin = 0;
  36.         data.clear();
  37.         minData.clear();
  38.     }
  39. };
  40.  
  41. int main() {
  42.     MinQueue q;
  43.     int n, k;
  44.     cin >> n >> k;
  45.     vector<int> a(n);
  46.     for (auto &x : a) {
  47.         cin >> x;
  48.     }
  49.     int len;
  50.     int ans = 0;
  51.     while (k--) {
  52.         q.clear();
  53.         cin >> len;
  54.         for (int i = 0; i < len; ++i) {
  55.             q.push(a[i]);
  56.         }
  57.         int curAns = q.min();
  58.         for (int i = len; i < n; ++i) {
  59.             q.pop();
  60.             q.push(a[i]);
  61.             curAns = max(curAns, q.min());
  62.         }
  63.         ans += curAns;
  64.     }
  65.     cout << ans << '\n';
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement