153202025-02-18 11:28:21AblablablaSzitakötő (50 pont)cpp17Wrong answer 4/5057ms1984 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<int> pref(n + 1);
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + alap[i - 1];
    }

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

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

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

        dp[i] %= MOD;
    }


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

            int bal = pref[i];
            int 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]) << "\n";
}
SubtaskSumTestVerdictTimeMemory
base4/50
1Accepted0/01ms316 KiB
2Wrong answer0/057ms1844 KiB
3Accepted1/11ms316 KiB
4Accepted1/11ms316 KiB
5Wrong answer0/11ms316 KiB
6Accepted1/11ms316 KiB
7Accepted1/11ms316 KiB
8Wrong answer0/11ms316 KiB
9Wrong answer0/11ms316 KiB
10Wrong answer0/21ms316 KiB
11Wrong answer0/21ms316 KiB
12Wrong answer0/21ms316 KiB
13Wrong answer0/21ms316 KiB
14Wrong answer0/21ms336 KiB
15Wrong answer0/21ms648 KiB
16Wrong answer0/21ms316 KiB
17Wrong answer0/21ms316 KiB
18Wrong answer0/21ms316 KiB
19Wrong answer0/21ms500 KiB
20Wrong answer0/21ms500 KiB
21Wrong answer0/11ms316 KiB
22Wrong answer0/243ms1984 KiB
23Wrong answer0/239ms1740 KiB
24Wrong answer0/257ms1964 KiB
25Wrong answer0/252ms1844 KiB
26Wrong answer0/248ms1960 KiB
27Wrong answer0/226ms1964 KiB
28Wrong answer0/241ms1844 KiB
29Wrong answer0/235ms1960 KiB
30Wrong answer0/257ms1964 KiB
31Wrong answer0/243ms1844 KiB