115142024-10-15 19:40:35chucknorrisSzitakötő (50 pont)cpp17Wrong answer 49/5056ms2328 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; R = mid - 1;
        }
        else L = 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(i + 1, 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
base49/50
1Accepted0/01ms500 KiB
2Accepted0/056ms2192 KiB
3Accepted1/11ms324 KiB
4Accepted1/11ms320 KiB
5Wrong answer0/11ms320 KiB
6Accepted1/11ms320 KiB
7Accepted1/11ms320 KiB
8Accepted1/11ms320 KiB
9Accepted1/11ms320 KiB
10Accepted2/21ms320 KiB
11Accepted2/21ms320 KiB
12Accepted2/21ms508 KiB
13Accepted2/21ms320 KiB
14Accepted2/21ms320 KiB
15Accepted2/21ms320 KiB
16Accepted2/21ms320 KiB
17Accepted2/21ms320 KiB
18Accepted2/21ms320 KiB
19Accepted2/21ms320 KiB
20Accepted2/21ms508 KiB
21Accepted1/11ms332 KiB
22Accepted2/241ms2280 KiB
23Accepted2/241ms2104 KiB
24Accepted2/254ms2076 KiB
25Accepted2/250ms1752 KiB
26Accepted2/248ms1512 KiB
27Accepted2/226ms2152 KiB
28Accepted2/243ms2328 KiB
29Accepted2/235ms1852 KiB
30Accepted2/254ms2308 KiB
31Accepted2/245ms1388 KiB