138582025-01-08 23:46:13Vkrisztian01Szitakötő (50 pont)cpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/054ms4400 KiB
3Elfogadva1/11ms512 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva1/11ms404 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Elfogadva1/11ms316 KiB
9Elfogadva1/11ms316 KiB
10Elfogadva2/21ms316 KiB
11Elfogadva2/21ms316 KiB
12Elfogadva2/21ms316 KiB
13Elfogadva2/22ms316 KiB
14Elfogadva2/21ms316 KiB
15Elfogadva2/22ms440 KiB
16Elfogadva2/21ms316 KiB
17Elfogadva2/21ms316 KiB
18Elfogadva2/21ms316 KiB
19Elfogadva2/22ms508 KiB
20Elfogadva2/21ms316 KiB
21Elfogadva1/11ms316 KiB
22Elfogadva2/241ms3892 KiB
23Elfogadva2/241ms3568 KiB
24Elfogadva2/254ms4140 KiB
25Elfogadva2/250ms3412 KiB
26Elfogadva2/248ms2736 KiB
27Elfogadva2/225ms3720 KiB
28Elfogadva2/243ms4148 KiB
29Elfogadva2/235ms3124 KiB
30Elfogadva2/254ms4396 KiB
31Elfogadva2/243ms2740 KiB