251072026-02-17 23:00:30999Szitakötő (50 pont)cpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base16/50
1Elfogadva0/01ms500 KiB
2Hibás válasz0/050ms3380 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva1/11ms316 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Elfogadva1/11ms316 KiB
9Elfogadva1/11ms500 KiB
10Elfogadva2/21ms316 KiB
11Elfogadva2/21ms316 KiB
12Elfogadva2/21ms316 KiB
13Hibás válasz0/21ms316 KiB
14Hibás válasz0/21ms316 KiB
15Hibás válasz0/22ms316 KiB
16Hibás válasz0/21ms388 KiB
17Elfogadva2/21ms316 KiB
18Hibás válasz0/21ms316 KiB
19Hibás válasz0/22ms500 KiB
20Hibás válasz0/21ms316 KiB
21Elfogadva1/11ms316 KiB
22Hibás válasz0/237ms3520 KiB
23Hibás válasz0/239ms3516 KiB
24Hibás válasz0/250ms3516 KiB
25Hibás válasz0/248ms3516 KiB
26Hibás válasz0/248ms3376 KiB
27Hibás válasz0/221ms3516 KiB
28Hibás válasz0/239ms3380 KiB
29Hibás válasz0/235ms3516 KiB
30Hibás válasz0/250ms3380 KiB
31Hibás válasz0/246ms3380 KiB