153232025-02-18 11:29:57AblablablaSzitakötő (50 pont)cpp17Hibás válasz 8/5054ms2740 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--;

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

    vector<ll> dp(n);
    dp[0] = 2;
    for(ll i = 1; i < k; i++){
        ll bal = pref[i + 1];
        ll jobb = pref[k + 1] - pref[i + 1];

        dp[i] = dp[i - 1];

        if(bal <= jobb){
            dp[i] *= 2;
        }

        dp[i] %= MOD;
    }


    for(ll i = n - 1; 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;
            }
        }

        dp[i] = (i == n - 1 ? 2 : dp[i + 1]) + (ind == -1 ? 0 : dp[ind]);
        dp[i] %= MOD;
    }

    cout << ((k == 0 ? 0 : dp[k - 1]) * (k == n - 1 ? 2 : dp[k + 1])) % MOD << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base8/50
1Elfogadva0/01ms500 KiB
2Hibás válasz0/054ms2612 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Hibás válasz0/11ms316 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Hibás válasz0/11ms316 KiB
9Hibás válasz0/11ms316 KiB
10Hibás válasz0/21ms500 KiB
11Hibás válasz0/21ms372 KiB
12Hibás válasz0/21ms316 KiB
13Hibás válasz0/21ms328 KiB
14Hibás válasz0/21ms316 KiB
15Hibás válasz0/21ms316 KiB
16Hibás válasz0/21ms316 KiB
17Hibás válasz0/21ms316 KiB
18Hibás válasz0/21ms316 KiB
19Hibás válasz0/21ms500 KiB
20Hibás válasz0/21ms316 KiB
21Hibás válasz0/11ms508 KiB
22Hibás válasz0/241ms2732 KiB
23Hibás válasz0/241ms2732 KiB
24Hibás válasz0/254ms2724 KiB
25Hibás válasz0/250ms2732 KiB
26Elfogadva2/250ms2612 KiB
27Hibás válasz0/226ms2740 KiB
28Hibás válasz0/243ms2740 KiB
29Hibás válasz0/237ms2612 KiB
30Hibás válasz0/254ms2612 KiB
31Elfogadva2/243ms2728 KiB