251102026-02-17 23:21:31999Szitakötő (50 pont)cpp17Accepted 50/5048ms3528 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int binpow(int a,int b){
    if(b==0)return 1;
    if(b%2==1)return (binpow(a,b-1)*a)%(int)(1e9+7);
    int x=binpow(a,b/2);
    return (x*x)%(int)(1e9+7);
}

signed main() {
    int n,k;cin>>n>>k;
    k--;
    vector<int> v(n),pref(n);
    for(int i = 0;i<n;i++){
        cin>>v[i];
        pref[i]=v[i];
        if(i>0)pref[i]+=pref[i-1];
    }
    int indtillforced=k;
    for(int i = k-1;i>=0;i--){
        if(pref[k]-pref[i]>=pref[i]){
            indtillforced=i+1;
            break;
        }
    }
    int w1=binpow(2,indtillforced);
    vector<int> dp(n+2),dppref(n+2);
    dp[n]=1;
    dppref[n]=1;
    int j = n-1;
    for(int i = n-1;i>k;i--){
        while(j>=i&&pref[j]-pref[i-1]>=pref[i-1])j--;
        if(j<i)dp[i]=0;
        else dp[i]=(dppref[i+1]-dppref[j+2]+(j==n-1?1:0)+(int)(1e9+7))%(int)(1e9+7);
        dppref[i]=(dp[i]+dppref[i+1]+(int)(1e9+7))%(int)(1e9+7);
    }
    int w2=2;
    if(k!=n-1)w2=dp[k+1];
    /*for(int i : dp)cout<<i<<' ';
    cout<<endl;*/
    //cout<<w1<<' '<<w2<<endl;
    cout<<((k==0?0:w1)*(k==n-1?2:(w2+(int)(1e9+7))%(int)(1e9+7)))%(int)(1e9+7)<<endl;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms500 KiB
2Accepted0/048ms3380 KiB
3Accepted1/11ms316 KiB
4Accepted1/11ms316 KiB
5Accepted1/11ms316 KiB
6Accepted1/11ms316 KiB
7Accepted1/11ms316 KiB
8Accepted1/11ms316 KiB
9Accepted1/11ms316 KiB
10Accepted2/21ms316 KiB
11Accepted2/21ms392 KiB
12Accepted2/21ms316 KiB
13Accepted2/21ms316 KiB
14Accepted2/21ms316 KiB
15Accepted2/21ms316 KiB
16Accepted2/21ms316 KiB
17Accepted2/21ms316 KiB
18Accepted2/21ms316 KiB
19Accepted2/21ms316 KiB
20Accepted2/21ms316 KiB
21Accepted1/12ms512 KiB
22Accepted2/237ms3380 KiB
23Accepted2/237ms3520 KiB
24Accepted2/248ms3520 KiB
25Accepted2/248ms3524 KiB
26Accepted2/248ms3380 KiB
27Accepted2/220ms3528 KiB
28Accepted2/239ms3408 KiB
29Accepted2/235ms3380 KiB
30Accepted2/248ms3384 KiB
31Accepted2/245ms3380 KiB