În școala unde învață, Andrei și Bogdan cunosc alți N elevi, etichetați cu numerele 1, 2, …, N. Dintre cei N elevi, o parte sunt prietenii lui Andrei. O parte dintre cei N elevi sunt dușmanii lui Bogdan. Se cunosc atât tichetele prietenilor lui Andrei, cât și etichetele dușmanilor lui Bogdan. Directorul școlii dorește să organizeze o excursie la care să participe Andrei, Bogdan și S dintre cunoscuții acestora, astfel încât din grupul celor S elevi să facă parte cel puțin K1 dintre prietenii lui Andrei și cel mult K2 dintre dușmanii lui Bogdan. Dorind să evite evenimente neplăcute, directorul va alege cei S elevi astfel încât numărul total al absențelor acumulate de aceștia, notat Sm, să fie minim.

Cerința

Cunoscând valorile N, S, K1, K2, etichetele prietenilor lui Andrei, etichetele dușmanilor lui Bogdan, precum și numărul absențelor acumulate de fiecare dintre cei N elevi, determinați valoarea Sm obținută pentru un grup ce satisface condițiile de mai sus.

Date de intrare

Datele de intrare se citesc din fișierul text grup1.in, cu structura următoare:

pe prima linie se află valorile naturale N, S, K1, K2, separate prin câte un spațiu, cu semnificațiile din enunț;
pe a doua linie se află valorile a[1], a[2], …, a[N], separate prin câte un spațiu, reprezentând numărul absențelor acumulate de fiecare dintre cei N elevi;
pe a treia linie se află un șir compus din N caractere din mulțimea {0, 1}, neseparate prin spații. Dacă al i-lea caracter din șir este caracterul 1, atunci elevul cu eticheta i este prieten cu Andrei;
pe a patra linie se află un șir compus din N caractere din mulțimea {0, 1}, neseparate prin spații. Dacă al i-lea caracter din șir este caracterul 1, atunci elevul cu eticheta i este dușmanul lui Bogdan.

Date de ieșire

Pe prima linie din fișierul text grup1.out se va tipări valoarea Sm.

Restricții și precizări

2 ≤ N ≤ 100 000
1 ≤ a[i] ≤ 1 000 000 000, pentru orice i = 1..N
Andrei și Bogdan nu fac parte din grupul celor S elevi selectați;

Exemplu

grup1.in

7 4 3 2
1 2 3 4 5 6 7
0010110
0011010

grup1.out

Explicație

Elevii selectați în grup sunt cei cu etichetele 1, 3, 5, 6. Numarul total de absențe Sm = 1+3+5+6 = 15. Prietenii lui Andrei, selectați în grup, sunt 3, 5 și 6. Dușmanii lui Bogdan, selectați în grup, sunt 3 și 6.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema grup1:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <climits>

using namespace std;

int main() {
    ifstream cin("grup1.in");
    ofstream cout("grup1.out");

    int N, S, K1, K2; assert(cin >> N >> S >> K1 >> K2);
    assert(1 <= N && N <= 100 * 1000);
    assert(0 <= K1 && K1 <= S);
    assert(0 <= K2 && K2 <= S);
    assert(1 <= S && S <= N);

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        assert(cin >> A[i]);
        assert(1 <= A[i] && A[i] <= 1000 * 1000 * 1000);
    }

    string friendsA, friendsB;
    assert(cin >> friendsA >> friendsB);
    assert(int(friendsA.size()) == N);
    assert(int(friendsB.size()) == N);
    for (auto &c : friendsA)
        assert(c == '0' || c == '1');
    for (auto &c : friendsB) {
        assert(c == '0' || c == '1');
        c ^= '0' ^ '1';
    }

    K2 = S - K2;
    vector<int> have[4];
    for (int i = 0; i < N; ++i) {
        int mask = 0;
        if (friendsA[i] == '1')
            mask ^= 1;
        if (friendsB[i] == '1')
            mask ^= 2;
        have[mask].push_back(A[i]);
    }

    for (int i = 0; i < 4; ++i)
        sort(have[i].begin(), have[i].end());

    int x[4] = {0, 0, 0, 0};
    int64_t total_sum = 0;
    int64_t answer = numeric_limits<int64_t>::max();

    for (x[3] = -1; x[3] <= S && x[3] < int(have[3].size()); ) {
        if (x[3] == -1)
            ++x[3];
        else
            total_sum += have[3][x[3]++];
        if (K1 - x[3] > int(have[1].size()))
            continue; // not enough friends for A
        if (K2 - x[3] > int(have[2].size()))
            continue; // not enough friends for B
        if (K1 - x[3] + K2 - x[3] + x[3] > S) // need to many people
            continue;

        if (x[3] + int(have[0].size()) + int(have[1].size()) + int(have[2].size()) < S) { // not enough people to get S
            continue;
        }

        for (int i = 0; i < 3; ++i)
            if (x[i] > 0) {
                total_sum -= have[i][--x[i]];
            }

        while (x[3] + x[1] < K1) {
            total_sum += have[1][x[1]++];
        }
        while (x[3] + x[2] < K2) {
            total_sum += have[2][x[2]++];
        }

        while (x[0] + x[1] + x[2] + x[3] < S) {
            int best = numeric_limits<int>::max();
            int where = 0;
            for (int j = 0; j < 3; ++j)
                if (x[j] < int(have[j].size()) && have[j][x[j]] < best) {
                    best = have[j][x[j]];
                    where = j;
                }
            total_sum += have[where][x[where]++];
        }

        answer = min(answer, total_sum);
    }

    if (answer == numeric_limits<int64_t>::max()) {
        answer = 1LL << 62;
    }

    cout << answer << "\n";
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2467 grup1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2467 grup1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2467 grup1