138582025-01-08 23:46:13Vkrisztian01Szitakötő (50 pont)cpp17Accepted 50/5054ms4400 KiB
#include <iostream>
#include<bits/stdc++.h>
typedef long long ll ;
const ll mod = 1e9 + 7 ;

using namespace std;

int main()
{
    ll n , k ;
    cin >> n >> k ;

    vector<ll> v(n + 1) ;
    vector<ll> s(n + 1) ;
    s[0] = 0 ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> v[i] ;
        s[i] = s[i - 1] + v[i] ;
    }

    ll ans = 1 ;
    for(int i = 1 ; i < k ; i++)
    {
        if(2 * s[i] <= s[k])
        {
            ans *= 2 ;
            ans %= mod ;
        }
    }

    ll dp[n + 6] ;
    ll S[n + 6] ;

    dp[k] = ans ;
    S[k] = ans ;
    S[k - 1] = 0 ;
    dp[k - 1] = 0 ;

    for(int i = k + 1 ; i <= n ; i++)
    {
        int tl = k + 1 , tr = i ;
        while(tr != tl)
        {
            int tm = (tl + tr) / 2 ;

            if(s[tm - 1] > s[i] - s[tm - 1])
                tr = tm ;
            else
                tl = tm + 1 ;
        }

        if(s[i - 1] <= v[i])
        {
            dp[i] = 0 ;
        }
        else
        {
            dp[i] = S[i - 1] - S[tl - 2] ;
        }


        if(dp[i] < 0)
            dp[i] += mod ;
        dp[i] %= mod ;
        S[i] = S[i - 1] + dp[i] ;
        if(S[i] < 0)
            S[i] += mod ;
        S[i] %= mod ;

    }

    dp[n] *= 2 ;
    dp[n] %= mod ;

    cout << dp[n] ;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/054ms4400 KiB
3Accepted1/11ms512 KiB
4Accepted1/11ms316 KiB
5Accepted1/11ms404 KiB
6Accepted1/11ms316 KiB
7Accepted1/11ms316 KiB
8Accepted1/11ms316 KiB
9Accepted1/11ms316 KiB
10Accepted2/21ms316 KiB
11Accepted2/21ms316 KiB
12Accepted2/21ms316 KiB
13Accepted2/22ms316 KiB
14Accepted2/21ms316 KiB
15Accepted2/22ms440 KiB
16Accepted2/21ms316 KiB
17Accepted2/21ms316 KiB
18Accepted2/21ms316 KiB
19Accepted2/22ms508 KiB
20Accepted2/21ms316 KiB
21Accepted1/11ms316 KiB
22Accepted2/241ms3892 KiB
23Accepted2/241ms3568 KiB
24Accepted2/254ms4140 KiB
25Accepted2/250ms3412 KiB
26Accepted2/248ms2736 KiB
27Accepted2/225ms3720 KiB
28Accepted2/243ms4148 KiB
29Accepted2/235ms3124 KiB
30Accepted2/254ms4396 KiB
31Accepted2/243ms2740 KiB