154422025-02-19 16:16:31tomi7Szitakötő (50 pont)cpp17Wrong answer 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';
}
SubtaskSumTestVerdictTimeMemory
base3/50
1Accepted0/01ms508 KiB
2Wrong answer0/059ms1844 KiB
3Accepted1/11ms508 KiB
4Wrong answer0/11ms316 KiB
5Accepted1/11ms316 KiB
6Wrong answer0/11ms316 KiB
7Wrong answer0/11ms316 KiB
8Wrong answer0/11ms372 KiB
9Wrong answer0/11ms316 KiB
10Wrong answer0/21ms316 KiB
11Wrong answer0/21ms512 KiB
12Wrong answer0/21ms500 KiB
13Wrong answer0/21ms496 KiB
14Wrong answer0/21ms316 KiB
15Wrong answer0/21ms500 KiB
16Wrong answer0/21ms508 KiB
17Wrong answer0/21ms316 KiB
18Wrong answer0/21ms316 KiB
19Wrong answer0/21ms316 KiB
20Wrong answer0/21ms508 KiB
21Accepted1/11ms316 KiB
22Wrong answer0/237ms1844 KiB
23Wrong answer0/239ms1964 KiB
24Wrong answer0/259ms1968 KiB
25Wrong answer0/254ms1956 KiB
26Wrong answer0/250ms1968 KiB
27Wrong answer0/223ms1972 KiB
28Wrong answer0/241ms1964 KiB
29Wrong answer0/235ms1964 KiB
30Wrong answer0/259ms1840 KiB
31Wrong answer0/246ms1844 KiB