#include #include using namespace std; #define MAXN 200000 //Halda o H prvcich, pozice v poli cislovany od nuly //Uzel i ma syny 2i+1, 2i+2 //Otec uzlu i je uzel (i-1)/2 (celociselne deleni) int halda[MAXN], H; //Prvek na pozici p je prohazovan s prvky nad nim, //dokud neni splnena podminka usporadani prvku v halde void probublej_nahoru(int p) { while (p > 0 && halda[p] < halda[(p-1)/2]) { swap(halda[p], halda[(p-1)/2]); p = (p-1)/2; } } //Bublani dolu je slozitejsi v tom, //ze je treba zkontrolovat oba syny //a vybrat mensiho z nich void probublej_dolu(int p) { while (p <= (H-1)/2) { int mensi = 2*p + 1; if (2*p + 2 < H && halda[mensi] > halda[2*p + 2]) mensi = 2*p + 2; if (halda[mensi] < halda[p]) { swap(halda[p], halda[mensi]); p = mensi; } else break; } } void odstran_minimum() { halda[0] = halda[H-1]; H--; probublej_dolu(0); } void vloz_do_haldy(int v) { halda[H++] = v; probublej_nahoru(H-1); } int N; int main() { scanf("%d", &N); int v; char c[5]; for (int i = 0; i < N-1; i++) { scanf("%s %d\n", c, &v); if (c[0] == 'D') vloz_do_haldy(v); else { while (H >= v && H > 0) odstran_minimum(); } } //Nyni jsme zabili, co jsme mohli //Zkontrolujeme, zda je posledni princezna spokojena scanf("%s %d", c, &v); if (v > H) printf("NE\n"); else { int zisk = 0; for (int i = 0; i < H; i++) zisk += halda[i]; printf("ANO\n%d\n", zisk); } return 0; }