115152024-10-15 19:56:25chucknorrisSzitakötő (50 pont)cpp17Hibás válasz 49/5052ms2236 KiB
#include <iostream>
#define MOD 1000000007

using namespace std;

int N, K, a[100002];
long long s[100002], dp[100002];///dp[i]=ennyi jo kombinacio van N es i kozott
///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) % MOD;///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
base49/50
1Elfogadva0/01ms328 KiB
2Elfogadva0/052ms2116 KiB
3Elfogadva1/11ms328 KiB
4Elfogadva1/11ms332 KiB
5Hibás válasz0/11ms332 KiB
6Elfogadva1/11ms332 KiB
7Elfogadva1/11ms332 KiB
8Elfogadva1/11ms332 KiB
9Elfogadva1/11ms344 KiB
10Elfogadva2/21ms500 KiB
11Elfogadva2/21ms332 KiB
12Elfogadva2/21ms332 KiB
13Elfogadva2/21ms332 KiB
14Elfogadva2/21ms332 KiB
15Elfogadva2/21ms332 KiB
16Elfogadva2/21ms332 KiB
17Elfogadva2/21ms332 KiB
18Elfogadva2/22ms332 KiB
19Elfogadva2/22ms332 KiB
20Elfogadva2/21ms344 KiB
21Elfogadva1/11ms556 KiB
22Elfogadva2/241ms2136 KiB
23Elfogadva2/239ms2144 KiB
24Elfogadva2/252ms2200 KiB
25Elfogadva2/246ms1904 KiB
26Elfogadva2/245ms1520 KiB
27Elfogadva2/226ms2236 KiB
28Elfogadva2/241ms2232 KiB
29Elfogadva2/234ms1780 KiB
30Elfogadva2/250ms2116 KiB
31Elfogadva2/241ms1580 KiB