154422025-02-19 16:16:31tomi7Szitakötő (50 pont)cpp17Hibás válasz 3/5059ms1972 KiB
// Source: https://usaco.guide/general/io

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int MOD=1e9+7;

int main() {
	int n, k; cin>>n>>k;
    vector<int> a(n);
    vector<int> pref(n);
    int sum=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        pref[i]=sum;
    }
    int y=lower_bound(pref.begin(), pref.begin()+k-1, pref[k-1]/2)-pref.begin();
    vector<int> dp(n);
    vector<int> prefdp(n);
    if(k!=n){
        if(pref[k-1]>a[k]){
            dp[k]=1;
            prefdp[k]=1;
        }
    }
    for(int i=k+1;i<n;i++){
        int x=upper_bound(pref.begin(), pref.begin()+i, pref[i]/2)-pref.begin();
        dp[i]=(prefdp[i-1]-prefdp[x-1] + MOD) % MOD;
        prefdp[i]=(prefdp[i-1]+dp[i]) % MOD;
    }
    dp[n-1]*=2;
    dp[n-1]%=MOD;
    int x=1;
    for(int i=0;i<y;i++){
        x*=2;
        x%=MOD;
    }
    cout<<(dp[n-1]*x)%MOD<<'\n';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base3/50
1Elfogadva0/01ms508 KiB
2Hibás válasz0/059ms1844 KiB
3Elfogadva1/11ms508 KiB
4Hibás válasz0/11ms316 KiB
5Elfogadva1/11ms316 KiB
6Hibás válasz0/11ms316 KiB
7Hibás válasz0/11ms316 KiB
8Hibás válasz0/11ms372 KiB
9Hibás válasz0/11ms316 KiB
10Hibás válasz0/21ms316 KiB
11Hibás válasz0/21ms512 KiB
12Hibás válasz0/21ms500 KiB
13Hibás válasz0/21ms496 KiB
14Hibás válasz0/21ms316 KiB
15Hibás válasz0/21ms500 KiB
16Hibás válasz0/21ms508 KiB
17Hibás válasz0/21ms316 KiB
18Hibás válasz0/21ms316 KiB
19Hibás válasz0/21ms316 KiB
20Hibás válasz0/21ms508 KiB
21Elfogadva1/11ms316 KiB
22Hibás válasz0/237ms1844 KiB
23Hibás válasz0/239ms1964 KiB
24Hibás válasz0/259ms1968 KiB
25Hibás válasz0/254ms1956 KiB
26Hibás válasz0/250ms1968 KiB
27Hibás válasz0/223ms1972 KiB
28Hibás válasz0/241ms1964 KiB
29Hibás válasz0/235ms1964 KiB
30Hibás válasz0/259ms1840 KiB
31Hibás válasz0/246ms1844 KiB