Codeforces Round #208 (Div. 2) C. Dima and Containers
練習会で3人が挑んで2人が誤読した。誤読した。
C. Dima and Containers
問題
stack, queue 及び deque がひとつずつある。 以下のクエリが与えられる。取り出した数の総和を最大化せよ。
- 数$a_i \gt 0$が指定される。いずれかのcontainerにこれを追加する。
- それぞれのcontainerから要素をひとつずつ取り出す。既に空なら無視する。その後全てのcontainerを空にする。
解法
pushする数に関して、それをpopすることになるのかどうかを事前に判定しておく。
実装
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
int n; cin >> n;
vector<int> a(n); repeat (i,n) cin >> a[i];
vector<bool> used(n); {
priority_queue<pair<int,int> > q;
repeat (i,n) {
if (a[i] == 0) {
for (int j = 0; j < 3 and not q.empty(); ++ j) {
int weight, index; tie(weight, index) = q.top(); q.pop();
used[index] = true;
}
q = decltype(q)();
} else {
q.push(make_pair(a[i], i));
}
}
}
int j = 0;
repeat (i,n) {
if (a[i] == 0) {
cout << j;
if (j >= 1) cout << ' ' << "popStack";
if (j >= 2) cout << ' ' << "popQueue";
if (j >= 3) cout << ' ' << "popFront";
cout << endl;
j = 0;
} else {
if (used[i]) {
switch (j) {
case 0: cout << "pushStack" << endl; ++ j; break;
case 1: cout << "pushQueue" << endl; ++ j; break;
case 2: cout << "pushFront" << endl; ++ j; break;
}
} else {
cout << "pushBack" << endl;
}
}
}
return 0;
}