251072026-02-17 23:00:30999Szitakötő (50 pont)cpp17Wrong answer 16/5050ms3520 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 pow(int a,int b){
    if(b==0)return 1;
    if(b%2==1)return (pow(a,b-1)*a)%(int)(1e9+7);
    int x=pow(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=pow(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);
        dppref[i]=(dp[i]+dppref[i+1])%(int)(1e9+7);
    }
    int w2=2;
    if(k!=n-1)w2=dp[k+1];
    /*for(int i : dp)cout<<i<<' ';
    cout<<endl;*/
    cout<<((k==0?0:w1)*(k==n-1?2:w2))%(int)(1e9+7)<<endl;
}
SubtaskSumTestVerdictTimeMemory
base16/50
1Accepted0/01ms500 KiB
2Wrong answer0/050ms3380 KiB
3Accepted1/11ms316 KiB
4Accepted1/11ms316 KiB
5Accepted1/11ms316 KiB
6Accepted1/11ms316 KiB
7Accepted1/11ms316 KiB
8Accepted1/11ms316 KiB
9Accepted1/11ms500 KiB
10Accepted2/21ms316 KiB
11Accepted2/21ms316 KiB
12Accepted2/21ms316 KiB
13Wrong answer0/21ms316 KiB
14Wrong answer0/21ms316 KiB
15Wrong answer0/22ms316 KiB
16Wrong answer0/21ms388 KiB
17Accepted2/21ms316 KiB
18Wrong answer0/21ms316 KiB
19Wrong answer0/22ms500 KiB
20Wrong answer0/21ms316 KiB
21Accepted1/11ms316 KiB
22Wrong answer0/237ms3520 KiB
23Wrong answer0/239ms3516 KiB
24Wrong answer0/250ms3516 KiB
25Wrong answer0/248ms3516 KiB
26Wrong answer0/248ms3376 KiB
27Wrong answer0/221ms3516 KiB
28Wrong answer0/239ms3380 KiB
29Wrong answer0/235ms3516 KiB
30Wrong answer0/250ms3380 KiB
31Wrong answer0/246ms3380 KiB