249612026-02-17 10:13:22szjSzitakötő (50 pont)cpp17Accepted 50/5026ms3584 KiB
#include <bits/stdc++.h>
#define ll long long
ll lowkey = 1e9+7;
#define blugy %lowkey
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n, k, i, mer, mar=0, sum=1, p1, p2, p;
    cin >> n >> k;
    k;
    vector<ll> t(n+1), dp(n+1,0), cucc(n+1,0),s(n+1);
    s[0]=t[0];
    for(i=1; i<=n; i++)
    {
        cin >> t[i];
        s[i]=s[i-1]+t[i];
    }
    for(i=1; i<k; i++)if(2*s[i]<=s[k])sum=(sum<<1)blugy;
    cucc[k]=sum;
    dp[k]=sum;
    for(i=k+1; i<=n; i++)
    {
        p1=k+1;
        p2=i;
        while(p1!=p2)
        {
            p=(p1+p2)/2;
            if(2*s[p-1]>s[i])p2=p;
            else p1=p+1;
        }
        if(s[i-1]>t[i])dp[i]=cucc[i-1]-cucc[p1-2];
        if(dp[i]<0)dp[i]+=lowkey;
        dp[i]=dp[i]blugy;
        cucc[i]=cucc[i-1]+dp[i];
        if(cucc[i]<0)cucc[i]+=lowkey;
        cucc[i]=cucc[i]blugy;
    }
    cout << (2*dp[n])blugy;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/026ms3380 KiB
3Accepted1/11ms500 KiB
4Accepted1/11ms316 KiB
5Accepted1/11ms316 KiB
6Accepted1/11ms316 KiB
7Accepted1/11ms500 KiB
8Accepted1/11ms316 KiB
9Accepted1/11ms344 KiB
10Accepted2/21ms316 KiB
11Accepted2/21ms316 KiB
12Accepted2/21ms316 KiB
13Accepted2/21ms352 KiB
14Accepted2/21ms316 KiB
15Accepted2/21ms316 KiB
16Accepted2/21ms316 KiB
17Accepted2/21ms316 KiB
18Accepted2/22ms316 KiB
19Accepted2/21ms316 KiB
20Accepted2/21ms316 KiB
21Accepted1/11ms316 KiB
22Accepted2/221ms3380 KiB
23Accepted2/221ms3572 KiB
24Accepted2/226ms3564 KiB
25Accepted2/223ms3580 KiB
26Accepted2/218ms3576 KiB
27Accepted2/217ms3384 KiB
28Accepted2/223ms3380 KiB
29Accepted2/217ms3584 KiB
30Accepted2/225ms3516 KiB
31Accepted2/217ms3576 KiB