115132024-10-15 19:27:08chucknorrisSzitakötő (50 pont)cpp17Wrong answer 11/5056ms2340 KiB
#include <iostream>
#define MOD 1000000007

using namespace std;

int N, K, a[100002];
long long s[100002], dp[100002];
///rozsabimbo mindig balra indul, kulonben vege
///az osszes baloldalon levo larvat felfalja

int bs(int L, int R, int p){
    int ans = L;
    while(L <= R){
        int mid = L + (R - L) / 2;
        if(s[mid] - s[p] < s[p]){
            ans = mid; L = mid + 1;
        }
        else R = mid - 1;
    }
    return ans;
}
int main(){
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> a[i]; s[i] = s[i - 1] + a[i];
    }

    if(N == 1) cout << 2;
    else if(K == 1) cout << 0;
    else if(N == 3){
        if(K == 2){
            if(a[1] + a[2] < a[3]) cout << 0;
            else cout << 4;
        }
        else if(K == 3){
            if(a[1] + a[2] <= a[3]) cout << 8;
            else cout << 4;
        }
    }
    else{
        for(int i = K; i < N; i++){
            if(s[i] <= a[i + 1]){
                cout << 0; return 0;
            }
        }
        long long bal = 1, S = 0;
        int i = K;
        while(S < s[i]){
            S = S + a[i]; i = i - 1;
        }

        for( ; i >= 1; i--) bal = bal * 2 % MOD;

        if(K == N) {cout << bal * 2 % MOD; return 0;}

        long long jobb = 0, p2 = 1;///p2 = 2 hatvany
        S = 0;///N-tol i-ig az osszmeret
        for(i = N; i >= K; i--){
            ///az i-edik larvaig Rozsabimbo mindenkit felfalt
            if(s[i] > S) ///i-tol N-ig mar nem tudnak artani RB-nak
                jobb = p2;
            else{
                int pos = bs(K, N, i);///megkeressuk, hol a legkozelebbi larva ami csoportosulva (i, pos] kozott art RB
                jobb = (dp[i + 1] - dp[pos] + MOD) % MOD;///ennyi kombinacio nem arthat
            }
            dp[i] = dp[i + 1] + jobb;///ennyi kombinacio van i-ig ami nem art
            S = S + a[i]; p2 = p2 * 2 % MOD;
        }
        jobb = (dp[K] - dp[K + 1] + MOD) % MOD;
        cout << bal * jobb % MOD;
    }
    return 0;
}


SubtaskSumTestVerdictTimeMemory
base11/50
1Accepted0/01ms320 KiB
2Wrong answer0/056ms2104 KiB
3Accepted1/11ms320 KiB
4Accepted1/11ms320 KiB
5Wrong answer0/11ms320 KiB
6Accepted1/11ms320 KiB
7Accepted1/11ms320 KiB
8Wrong answer0/11ms320 KiB
9Wrong answer0/11ms320 KiB
10Wrong answer0/21ms584 KiB
11Wrong answer0/21ms320 KiB
12Wrong answer0/21ms500 KiB
13Wrong answer0/21ms500 KiB
14Accepted2/21ms332 KiB
15Wrong answer0/21ms320 KiB
16Wrong answer0/21ms320 KiB
17Wrong answer0/21ms320 KiB
18Wrong answer0/21ms320 KiB
19Wrong answer0/21ms320 KiB
20Wrong answer0/21ms320 KiB
21Accepted1/11ms508 KiB
22Wrong answer0/241ms2156 KiB
23Wrong answer0/241ms1936 KiB
24Wrong answer0/254ms2268 KiB
25Wrong answer0/250ms1756 KiB
26Accepted2/248ms1372 KiB
27Wrong answer0/226ms2292 KiB
28Wrong answer0/245ms2340 KiB
29Wrong answer0/237ms1860 KiB
30Wrong answer0/254ms2156 KiB
31Accepted2/245ms1460 KiB