113282024-08-10 03:40:55kukkermanMaximális szorzat (50 pont)cpp17Elfogadva 50/5063ms2040 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

void beolvas(std::istream &be, std::vector<int64_t> &v, int &k, int &b) {
    int n;
    be >> n >> k >> b;

    v.resize(n);
    for (auto &x : v) {
        be >> x;
    }
}

int feldolgoz(std::vector<int64_t> &a, int k, int b) {
    static const int64_t M = 1000000007;
    const auto n = static_cast<int>(a.size());

    sort(a.begin(), a.end());

    // Megkeressuk az elso nemnegativ szam poziciojat
    auto elso_nn = static_cast<int>(lower_bound(a.begin(), a.end(), 0) - a.begin());

    // Ha a feltetel tobb negativ szamot kovetel meg, mint ahany eredetileg a sorozatban
    // talalhato, akkor nincs megoldas.
    if (elso_nn < b) {
        return -1;
    }

    // A 0-hoz legkozelebb eso negativ szamtol kezdve megprobalunk annyit 0-ig novelni,
    // hogy pontosan az eloirt darabszamu maradjon.
    for (; elso_nn > b && k >= 0; elso_nn--) {
        // Levonjuk 'k'-bol az aktualis negativ szam 0-ig novelesenek koltseget.
        k += static_cast<int>(a[elso_nn - 1]);
        a[elso_nn - 1] = 0;
    }

    // Ha nincs elegendo valasztasunk ahhoz, hogy "eltuntessuk" a megfelelo darabszamu
    // negativ szamot, akkor nincs megoldas.
    if (k < 0) {
        return -1;
    }

    // Ha az osszes megmaradt szam negativ, akkor nincs mas lehetoseg, mint ezek kozott
    // szetosztani 'k'-t, ami az ossz szorzat csokkenesevel fog jarni. Azonban ebben
    // az esetben is ugy jarunk a legjobban, ha a legkisebbol a legnagyobb fele haladva
    // osztjuk szet 'k'-t. Mivel a szetosztas az [elso_nn; n - 1] intervallumon tortenik,
    // ezert egyszeruen nullazzuk 'elso_nn'-t.
    if (elso_nn == n) {
        elso_nn = 0;

        // Mivelott tovabbmennenk ellenorizzuk, hogy lehetseges-e ugy szetosztani 'k'-t,
        // hogy mindegyik elem negativ maradjon.
        int64_t s = k;
        for (int i = 0; i < n && s >= 0; i++) {
            // Egy negativ szamot (x) maximum '-x - 1'-szer novelhetunk meg ugy, hogy
            // negativ maradjon, azaz maskeppen fogalmazva: maximum '-x - 1' egyseget
            // "kolthetunk" el ra: s -= -x - 1  =>  s -= -(x + 1)  =>  s += x + 1
            s += a[i] + 1;
        }
        if (s > 0) {
            // Tobb egysegunk van, mint amennyi ahhoz kell, hogy az osszes negativ
            // szambol -1 legyen. Ha ennel akar egyetlen egyseggel tobbet koltunk,
            // akkor legalabb az egyik negativ szambol 0 lesz, ami azt jelenti,
            // hogy kevesebb negativ szamunk lesz az eloirtnal, ezert ebben az
            // esetben nincs megoldas.
            return -1;
        }
    }

    // Kiszamitjuk az elso nemnegativ szamtol kezdodoen egeszen a sorozat vegeig az egyes
    // elemek osszeget:
    // bal_osszeg[i] = az elso 'i' db. elem osszege az 'elso_nn' indextol kezdodoen
    std::vector<int64_t> bal_osszeg(n - elso_nn + 1, 0);
    for (int i = elso_nn; i < n; i++) {
        bal_osszeg[i - elso_nn + 1] = bal_osszeg[i - elso_nn] + a[i];
    }

    // Binaris kereses segitsegevel megkeressuk az elso olyan elem poziciojat,
    // amennyire mar eppen nem potolhatok ki a sorozat elemei az elso nemnegativ
    // elemtol kezdodoen. Pl.:
    // 
    // Legyen a = { -2, -1, 1, 3, 4 }, k = 3
    // 
    // Az elso nemnegativ elem pozicioja: elso_nn = 2. A sorozat kipotlasanak
    // a koltsege a 3. pozicioig 2 egyseg:  a = { -2, -1, 1 + 2, 3,     4 },
    // azonban a 4. pozicioig mar 4 egyseg: a = { -2, -1, 1 + 3, 3 + 1, 4 },
    // azaz a 4. az elso olyan pozicio, ameddig mar eppen nem potolhato ki 'k'
    // koltsegert.
    int eleje = elso_nn, vege = n;
    while (eleje < vege) {
        const auto kozep = eleje + (vege - eleje) / 2;
        // Az [elso_nn; kozep] indexu elemek 'a[kozep]'-re valo kipotlasanak koltsege.
        const auto koltseg = a[kozep] * (kozep - elso_nn + 1) - bal_osszeg[kozep - elso_nn + 1];

        if (k < koltseg) {
            vege = kozep;

        } else {
            eleje = kozep + 1;
        }
    }

    // Levonunk 'k'-bol annyit, amennyi elegendo az [elso_nn; vege - 1] sorszamu elemek
    // a[vege - 1]-re valo kipotlasahoz. Ekkor az osszes elem az [elso_nn; vege - 1]
    // tartomanyban egyenlo lesz a[vege - 1]-gyel.
    k -= static_cast<int>(a[vege - 1] * (vege - elso_nn) - bal_osszeg[vege - elso_nn]);

    // Kiszamitjuk, hogy a kipotlas utan maximum mennyire tudjuk az osszes elemet
    // az [elso_nn; vege - 1] tartomanyban megnovelni.
    const auto max_elem = a[vege - 1] + k / (vege - elso_nn);

    // Elkezdjuk kiszamitani a modositott vektor elemeinek a szorzatat, ugyelve arra,
    // hogy ne tortenjen tulcsordulas a szorzas soran.
    int64_t s = 1;

    // Osszeszorozzuk a megmaradt negativ elemeket.
    int i;
    for (i = 0; i < elso_nn; i++) {
        s = (s * -a[i]) % M;
    }

    // Osszesen 'k % (vege - elso_nn)' db. olyan elem lesz, amely a korabban kiszamitott
    // maximumon felul tovabbi egy egyseggel novelhato.
    for (auto j = k % (vege - elso_nn); j > 0; j--) {
        s = s * (max_elem + 1) % M;
        i++;
    }

    // A maradek elemek erteke 'max_elem' lesz egeszen 'vege - 1'-ig. 
    for (; i < vege; i++) {
        s = s * max_elem % M;
    }

    // A vektor vegen pedig azok az elemek maradnak, amelyeket mar nem lehet kipotolni,
    // mert tulsagosan nagyok.
    for (; i < n; i++) {
        s = s * a[i] % M;
    }

    return static_cast<int>(s);
}

int main() {
    std::vector<int64_t> v;
    int k, b;
    beolvas(std::cin, v, k, b);

    std::cout << feldolgoz(v, k, b) << '\n';

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/02ms356 KiB
2Elfogadva0/02ms356 KiB
3Elfogadva0/02ms504 KiB
4Elfogadva0/03ms352 KiB
5Elfogadva0/06ms484 KiB
6Elfogadva2/23ms504 KiB
7Elfogadva2/23ms360 KiB
8Elfogadva2/23ms256 KiB
9Elfogadva2/23ms384 KiB
10Elfogadva2/27ms500 KiB
11Elfogadva2/256ms1836 KiB
12Elfogadva1/159ms1820 KiB
13Elfogadva1/13ms504 KiB
14Elfogadva1/17ms612 KiB
15Elfogadva1/123ms740 KiB
16Elfogadva1/124ms868 KiB
17Elfogadva1/123ms740 KiB
18Elfogadva1/113ms1168 KiB
19Elfogadva1/146ms1980 KiB
20Elfogadva1/134ms2040 KiB
21Elfogadva1/163ms1808 KiB
22Elfogadva1/126ms1272 KiB
23Elfogadva1/161ms1436 KiB
24Elfogadva1/157ms1692 KiB
25Elfogadva2/22ms356 KiB
26Elfogadva2/27ms484 KiB
27Elfogadva2/232ms1124 KiB
28Elfogadva1/132ms1168 KiB
29Elfogadva2/225ms740 KiB
30Elfogadva1/161ms1144 KiB
31Elfogadva1/143ms1208 KiB
32Elfogadva2/23ms356 KiB
33Elfogadva2/261ms996 KiB
34Elfogadva1/161ms1124 KiB
35Elfogadva2/261ms1132 KiB
36Elfogadva2/261ms1272 KiB
37Elfogadva2/261ms1124 KiB
38Elfogadva2/261ms1268 KiB
39Elfogadva1/12ms356 KiB