113882024-08-31 17:50:44kukkermanZebra (75 pont)cpp17Elfogadva 75/754ms588 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

void beolvas(std::istream &be, std::vector<int> &irany, std::vector<int> &erkezes) {
    int n;
    be >> n;

    irany.resize(n);
    for (auto &i : irany) {
        be >> i;
    }

    erkezes.resize(n);
    for (auto &e : erkezes) {
        be >> e;
    }
}

void feldolgoz(const std::vector<int> &irany, const std::vector<int> &erkezes) {
    const auto n = static_cast<int>(irany.size());

    std::vector<int> bal, jobb;
    for (int i = 0; i < n; i++) {
        if (irany[i] == 0) {
            bal.push_back(erkezes[i]);
        } else {
            jobb.push_back(erkezes[i]);
        }
    }

    sort(bal.begin(), bal.end());
    sort(jobb.begin(), jobb.end());

    const auto bal_db = static_cast<int>(bal.size());
    const auto jobb_db = static_cast<int>(jobb.size());

    std::vector<int> bal_ossz(bal_db + 1);
    for (int i = 0; i < bal_db; i++) {
        bal_ossz[i + 1] = bal_ossz[i] + bal[i];
    }

    std::vector<int> jobb_ossz(jobb_db + 1);
    for (int i = 0; i < jobb_db; i++) {
        jobb_ossz[i + 1] = jobb_ossz[i] + jobb[i];
    }

    std::vector<std::vector<int>> dp(bal_db + 1, std::vector<int>(jobb_db + 1, -1));
    dp[0][0] = 0;

    for (int utolso_bal = 0; utolso_bal < bal_db; utolso_bal++) {
        for (int utolso_jobb = 0; utolso_jobb < jobb_db; utolso_jobb++) {
            const auto utolso_idopont = std::max(bal[utolso_bal], jobb[utolso_jobb]);

            auto min_varakozas = std::numeric_limits<int>::max();
            for (int elso_bal = 0; elso_bal <= utolso_bal; elso_bal++) {
                for (int elso_jobb = 0; elso_jobb <= utolso_jobb; elso_jobb++) {
                    if (dp[elso_bal][elso_jobb] == -1) {
                        continue;
                    }

                    const auto bal_ossz_varakozas  = utolso_idopont * (utolso_bal  - elso_bal  + 1) - (bal_ossz [utolso_bal + 1 ] - bal_ossz [elso_bal ]);
                    const auto jobb_ossz_varakozas = utolso_idopont * (utolso_jobb - elso_jobb + 1) - (jobb_ossz[utolso_jobb + 1] - jobb_ossz[elso_jobb]);

                    min_varakozas = std::min(min_varakozas,
                                             dp[elso_bal][elso_jobb] + bal_ossz_varakozas + jobb_ossz_varakozas);
                }
            }

            dp[utolso_bal + 1][utolso_jobb + 1] = min_varakozas;
        }
    }

    std::cout << dp[bal_db][jobb_db] << '\n';
}

int main() {
    std::vector<int> irany, erkezes;
    beolvas(std::cin, irany, erkezes);

    feldolgoz(irany, erkezes);

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base75/75
1Elfogadva0/03ms588 KiB
2Elfogadva0/04ms564 KiB
3Elfogadva5/53ms512 KiB
4Elfogadva5/53ms416 KiB
5Elfogadva5/53ms360 KiB
6Elfogadva5/53ms360 KiB
7Elfogadva5/53ms376 KiB
8Elfogadva5/53ms376 KiB
9Elfogadva5/54ms488 KiB
10Elfogadva5/54ms504 KiB
11Elfogadva5/54ms384 KiB
12Elfogadva5/54ms376 KiB
13Elfogadva5/54ms360 KiB
14Elfogadva5/54ms528 KiB
15Elfogadva5/54ms360 KiB
16Elfogadva5/54ms384 KiB
17Elfogadva5/54ms376 KiB