115122024-10-15 19:08:04chucknorrisSzitakötő (50 pont)cpp17Hibás válasz 11/5052ms2300 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 - 1] < 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;
}


RészfeladatÖsszpontTesztVerdiktIdőMemória
base11/50
1Elfogadva0/01ms352 KiB
2Hibás válasz0/052ms2184 KiB
3Elfogadva1/11ms500 KiB
4Elfogadva1/11ms512 KiB
5Hibás válasz0/11ms332 KiB
6Elfogadva1/11ms396 KiB
7Elfogadva1/11ms368 KiB
8Hibás válasz0/11ms332 KiB
9Hibás válasz0/11ms332 KiB
10Hibás válasz0/21ms332 KiB
11Hibás válasz0/21ms332 KiB
12Hibás válasz0/21ms332 KiB
13Hibás válasz0/21ms320 KiB
14Elfogadva2/21ms332 KiB
15Hibás válasz0/21ms332 KiB
16Hibás válasz0/21ms332 KiB
17Hibás válasz0/21ms332 KiB
18Hibás válasz0/21ms524 KiB
19Hibás válasz0/21ms508 KiB
20Hibás válasz0/21ms508 KiB
21Elfogadva1/11ms332 KiB
22Hibás válasz0/241ms2116 KiB
23Hibás válasz0/239ms2024 KiB
24Hibás válasz0/252ms2300 KiB
25Hibás válasz0/246ms1708 KiB
26Elfogadva2/246ms1464 KiB
27Hibás válasz0/225ms2116 KiB
28Hibás válasz0/243ms2124 KiB
29Hibás válasz0/234ms1760 KiB
30Hibás válasz0/252ms2296 KiB
31Elfogadva2/241ms1516 KiB