251102026-02-17 23:21:31999Szitakötő (50 pont)cpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms500 KiB
2Elfogadva0/048ms3380 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva1/11ms316 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Elfogadva1/11ms316 KiB
9Elfogadva1/11ms316 KiB
10Elfogadva2/21ms316 KiB
11Elfogadva2/21ms392 KiB
12Elfogadva2/21ms316 KiB
13Elfogadva2/21ms316 KiB
14Elfogadva2/21ms316 KiB
15Elfogadva2/21ms316 KiB
16Elfogadva2/21ms316 KiB
17Elfogadva2/21ms316 KiB
18Elfogadva2/21ms316 KiB
19Elfogadva2/21ms316 KiB
20Elfogadva2/21ms316 KiB
21Elfogadva1/12ms512 KiB
22Elfogadva2/237ms3380 KiB
23Elfogadva2/237ms3520 KiB
24Elfogadva2/248ms3520 KiB
25Elfogadva2/248ms3524 KiB
26Elfogadva2/248ms3380 KiB
27Elfogadva2/220ms3528 KiB
28Elfogadva2/239ms3408 KiB
29Elfogadva2/235ms3380 KiB
30Elfogadva2/248ms3384 KiB
31Elfogadva2/245ms3380 KiB