153302025-02-18 12:29:45AblablablaSzitakötő (50 pont)cpp17Elfogadva 50/5056ms4280 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;

ll hatvany(ll a){
    ll vissza = 1;
    ll akt = 2;

    for(ll i = 0; i < 31; i++){
        if(a & (1 << i)){
            vissza *= akt;
            vissza %= MOD;
        }

        akt *= akt;
        akt %= MOD;
    }

    return vissza;
}

int main()
{
    ll n, k;
    cin >> n >> k;
    k--;

    if(k == 0){
        cout << "0\n";
        return 0;
    }

    vector<ll> alap(n);
    for(ll &x : alap) cin >> x;

    vector<ll> pref(n + 1);
    for(ll i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + alap[i - 1];
    }

    ll l = 0, r = k - 1;
    ll elol = 0;
    while(l <= r){
        ll mid = (l + r) / 2;

        ll bal = pref[mid + 1];
        ll jobb = pref[k + 1] - pref[mid + 1];

        if(bal <= jobb){
            l = mid + 1;
            elol = mid;
        } else{
            r = mid - 1;
        }
    }

    elol = hatvany(elol + 1);

    vector<ll> balra(n), jobbra(n), suf(n + 1);
    if(k != n - 1){
        if(pref[n - 1] > alap[n - 1]){
            balra[n - 1] = 2;
            jobbra[n - 1] = 0;
            suf[n - 1] = 2;
        } else{
            cout << "0\n";
            return 0;
        }

        for(ll i = n - 2; i > k; i--){
            ll l = i + 1, r = n - 1;
            ll ind = -1;
            while(l <= r){
                ll mid = (l + r) / 2;

                ll bal = pref[i];
                ll jobb = pref[mid + 1] - pref[i];

                if(bal > jobb){
                    ind = mid;
                    l = mid + 1;
                } else{
                    r = mid - 1;
                }
            }

            if(pref[i] > alap[i]){
                balra[i] = (balra[i + 1] + jobbra[i + 1]) % MOD;
                suf[i] = (suf[i + 1] + balra[i]) % MOD;
            } else{
                cout << "0\n";
                return 0;
            }

            if(ind != -1){
                jobbra[i] = (suf[i + 1] - suf[ind + 1] + MOD) % MOD;
            } else{
                jobbra[i] = 0;
            }
        }
    }

    ll a = (k == n - 1 ? 2 : (balra[k + 1] + jobbra[k + 1])) % MOD;

    cout << (elol * a) % MOD << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/056ms4148 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva1/11ms316 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Elfogadva1/11ms316 KiB
9Elfogadva1/11ms316 KiB
10Elfogadva2/21ms316 KiB
11Elfogadva2/21ms316 KiB
12Elfogadva2/21ms316 KiB
13Elfogadva2/21ms316 KiB
14Elfogadva2/21ms320 KiB
15Elfogadva2/21ms316 KiB
16Elfogadva2/21ms404 KiB
17Elfogadva2/21ms316 KiB
18Elfogadva2/21ms316 KiB
19Elfogadva2/21ms316 KiB
20Elfogadva2/21ms556 KiB
21Elfogadva1/11ms316 KiB
22Elfogadva2/243ms4280 KiB
23Elfogadva2/243ms4264 KiB
24Elfogadva2/254ms4264 KiB
25Elfogadva2/250ms4268 KiB
26Elfogadva2/250ms4264 KiB
27Elfogadva2/232ms4268 KiB
28Elfogadva2/246ms4272 KiB
29Elfogadva2/237ms4268 KiB
30Elfogadva2/256ms4148 KiB
31Elfogadva2/245ms4268 KiB