Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- class MinQueue {
- private:
- vector<int> data;
- size_t dataBegin;
- vector<int> minData;
- size_t minDataBegin;
- public:
- void push(int val) {
- data.push_back(val);
- while (minData.size() > minDataBegin && minData.back() > val) {
- minData.pop_back();
- }
- minData.push_back(val);
- }
- int min() {
- return minData[minDataBegin];
- }
- void pop() {
- if (minData[minDataBegin] == data[dataBegin++]) {
- ++minDataBegin;
- }
- }
- void clear() {
- dataBegin = minDataBegin = 0;
- data.clear();
- minData.clear();
- }
- };
- int main() {
- MinQueue q;
- int n, k;
- cin >> n >> k;
- vector<int> a(n);
- for (auto &x : a) {
- cin >> x;
- }
- int len;
- int ans = 0;
- while (k--) {
- q.clear();
- cin >> len;
- for (int i = 0; i < len; ++i) {
- q.push(a[i]);
- }
- int curAns = q.min();
- for (int i = len; i < n; ++i) {
- q.pop();
- q.push(a[i]);
- curAns = max(curAns, q.min());
- }
- ans += curAns;
- }
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement