113562024-08-22 22:52:06kukkermanSzitakötő (50 pont)cpp17Elfogadva 50/5056ms3216 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdint>

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

    larvak.resize(n);
    for (auto &l : larvak) {
        be >> l;
    }
}

int feldolgoz(int k, const std::vector<int> &larvak) {
    const uint64_t M = 1000000007;

    const auto n = static_cast<int>(larvak.size());

    if (n == 1) {
        return 2;
    }

    k--;
    if (k == 0) {
        return 0;
    }

    const auto m = std::max(k, n - k) + 2;
    std::vector<uint64_t> ketto_hatvany(m);
    ketto_hatvany[0] = 1;
    for (int i = 1; i < m; i++) {
        ketto_hatvany[i] = (ketto_hatvany[i - 1] * 2) % M;
    }

    std::vector<uint64_t> bal_osszeg(n);
    bal_osszeg[0] = larvak[0];
    for (int i = 1; i < n; i++) {
        bal_osszeg[i] = bal_osszeg[i - 1] + larvak[i];
    }

    const auto b = std::upper_bound(bal_osszeg.begin(),
                                    bal_osszeg.begin() + k,
                                    bal_osszeg[k],
                                    [](uint64_t b_k, uint64_t b_akt) {
                                        return b_k < b_akt * 2;
                                    }) - bal_osszeg.begin();
    const auto bal_db = ketto_hatvany[b];

    if (k == n - 1) {
        return static_cast<int>(ketto_hatvany[b + 1]);
    }

    std::vector<uint64_t> jobb_osszeg(n + 1);
    for (int i = n - 2; i >= k; i--) {
        const auto j = std::lower_bound(bal_osszeg.begin() + i + 1,
                                        bal_osszeg.end(),
                                        bal_osszeg[i] * 2) - bal_osszeg.begin();
        if (j == i + 1) {
            return 0;
        }

        const auto akt_db = j < n ? (M + jobb_osszeg[i + 1] - jobb_osszeg[j]) % M
            : ketto_hatvany[n - i - 1];
        jobb_osszeg[i] = (jobb_osszeg[i + 1] + akt_db) % M;
    }

    const auto jobb_db = (M + jobb_osszeg[k] - jobb_osszeg[k + 1]) % M;
    return static_cast<int>((bal_db * jobb_db) % M);
}

int main() {
    int k;
    std::vector<int> larvak;
    beolvas(std::cin, k, larvak);

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

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/02ms384 KiB
2Elfogadva0/056ms3104 KiB
3Elfogadva1/13ms356 KiB
4Elfogadva1/13ms384 KiB
5Elfogadva1/13ms384 KiB
6Elfogadva1/12ms504 KiB
7Elfogadva1/12ms356 KiB
8Elfogadva1/12ms400 KiB
9Elfogadva1/13ms280 KiB
10Elfogadva2/23ms384 KiB
11Elfogadva2/23ms256 KiB
12Elfogadva2/22ms356 KiB
13Elfogadva2/23ms228 KiB
14Elfogadva2/23ms488 KiB
15Elfogadva2/23ms504 KiB
16Elfogadva2/23ms400 KiB
17Elfogadva2/23ms504 KiB
18Elfogadva2/23ms376 KiB
19Elfogadva2/23ms372 KiB
20Elfogadva2/23ms356 KiB
21Elfogadva1/13ms228 KiB
22Elfogadva2/245ms3088 KiB
23Elfogadva2/243ms2844 KiB
24Elfogadva2/254ms3216 KiB
25Elfogadva2/250ms2660 KiB
26Elfogadva2/248ms2204 KiB
27Elfogadva2/227ms3092 KiB
28Elfogadva2/245ms3092 KiB
29Elfogadva2/237ms2832 KiB
30Elfogadva2/254ms3044 KiB
31Elfogadva2/246ms2328 KiB