113532024-08-22 04:07:50kukkermanSzitakötő (50 pont)cpp17Wrong answer 45/5056ms3164 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) + 1;
    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;
    }

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

    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];

    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;
}
SubtaskSumTestVerdictTimeMemory
base45/50
1Accepted0/03ms356 KiB
2Accepted0/056ms3044 KiB
3Accepted1/13ms356 KiB
4Accepted1/12ms512 KiB
5Accepted1/12ms228 KiB
6Accepted1/12ms360 KiB
7Wrong answer0/12ms228 KiB
8Accepted1/12ms356 KiB
9Accepted1/13ms384 KiB
10Accepted2/22ms228 KiB
11Accepted2/22ms356 KiB
12Accepted2/22ms384 KiB
13Accepted2/23ms632 KiB
14Accepted2/23ms500 KiB
15Accepted2/23ms504 KiB
16Accepted2/23ms508 KiB
17Accepted2/23ms356 KiB
18Accepted2/24ms504 KiB
19Accepted2/23ms228 KiB
20Accepted2/23ms356 KiB
21Accepted1/13ms504 KiB
22Accepted2/243ms3164 KiB
23Accepted2/243ms2984 KiB
24Accepted2/254ms3088 KiB
25Accepted2/250ms2724 KiB
26Wrong answer0/248ms1436 KiB
27Accepted2/227ms3044 KiB
28Accepted2/245ms3016 KiB
29Accepted2/237ms2788 KiB
30Accepted2/254ms3044 KiB
31Wrong answer0/245ms1508 KiB