242692026-02-07 16:43:01ercseferencSzitakötő (50 pont)cpp17Hibás válasz 49/5052ms1980 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    ll mod=1e9+7;
    int n,m; cin>>n>>m; m--;
    if(n==2){
        ll x,y; cin>>x>>y;
        if(m==0)cout<<0;
        if(m==1)cout<<4;}
    if(n==3){
        ll x,y,z; cin>>x>>y>>z;
        if(m==0)cout<<0;
        if(m==1)if(x+y>z)cout<<4;else cout<<0;
        if(m==2)if(x+y<=z)cout<<8; else cout<<4;
        return 0;}
    vector<ll>s(n);
    cin>>s[0];
    for(int i=1; i<n; i++){
        ll x; cin>>x;
        s[i]=s[i-1]+x;}
    ll t=s[m]-s[m-1];
    int poz=m-1;
    while(t<s[poz] && poz>=0){
        t+=s[poz]-s[poz-1];
        poz--;}
    ll ans=1;
    poz++;
    for(int i=0; i<poz; i++)
        ans=(ans*2)%mod;
    vector<ll>dp(n);
    dp[m-1]=0;
    dp[m]=ans;
    bool leh=1;
    for(int i=m+1; i<n; i++){
        int x=m+1,y=i;
        if(2*s[i-1]<s[i])leh=0;
        while(leh && x!=y){
            int k=(x+y)/2;
            if(2*s[k-1]>s[i])y=k;
            else x=k+1;}
        dp[i]=(2*dp[i-1]-dp[x-2])%mod;
        if(dp[i]<0)dp[i]+=mod;}
    if(leh){
        dp[n-1]-=dp[n-2];
        dp[n-1]=(dp[n-1]*2)%mod;
        if(dp[n-1]<0)dp[n-1]+=mod;
        cout<<dp[n-1];}
    else cout<<0;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base49/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/052ms1844 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva1/11ms316 KiB
5Elfogadva1/11ms316 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Elfogadva1/11ms316 KiB
9Elfogadva1/11ms316 KiB
10Elfogadva2/21ms508 KiB
11Elfogadva2/21ms316 KiB
12Elfogadva2/21ms316 KiB
13Elfogadva2/21ms316 KiB
14Elfogadva2/21ms404 KiB
15Elfogadva2/21ms508 KiB
16Elfogadva2/21ms552 KiB
17Elfogadva2/21ms316 KiB
18Elfogadva2/21ms316 KiB
19Elfogadva2/21ms552 KiB
20Elfogadva2/21ms508 KiB
21Hibás válasz0/11ms316 KiB
22Elfogadva2/239ms1956 KiB
23Elfogadva2/241ms1964 KiB
24Elfogadva2/252ms1844 KiB
25Elfogadva2/250ms1960 KiB
26Elfogadva2/248ms1980 KiB
27Elfogadva2/223ms1844 KiB
28Elfogadva2/241ms1960 KiB
29Elfogadva2/235ms1968 KiB
30Elfogadva2/252ms1956 KiB
31Elfogadva2/243ms1844 KiB