# Muffin Selection (muffin) 50/100

**URL:** <https://forum.olinfo.it/t/muffin-selection-muffin-50-100/6004>\
**Category:** Aiuto\
**Created:** [14 Gennaio 2020, 2:32pm UTC](https://forum.olinfo.it/t/muffin-selection-muffin-50-100/6004 "2020-01-14T14:32:06Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![ElenaLaura366](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/e274bd/32.png) [@ElenaLaura366](https://forum.olinfo.it/u/ElenaLaura366)\
**Post date:** [14 Gennaio 2020, 2:32pm UTC](https://forum.olinfo.it/t/muffin-selection-muffin-50-100/6004/1 "2020-01-14T14:32:06Z")

</div>

please help me. for this problem I get 50 out of 100 points.

```auto
#include <iostream>
using namespace std;
int t[1000001],n,k;
long long sv=0,sn=0;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>t[i];
    for(int i=0;i<k;++i)
        sv+=t[i];
    for(int i=1;i<=n-k+1;++i)
    {
        sn=0;
        for(int j=i;j<i+k;++j)
        {
            sn+=t[j];
        }
        if(sn>sv)
            sv=sn;
    }
    cout<<sv;
    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![davide991](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/f6c823/32.png) [@davide991](https://forum.olinfo.it/u/davide991)\
**Post date:** [14 Gennaio 2020, 5:56pm UTC](https://forum.olinfo.it/t/muffin-selection-muffin-50-100/6004/2 "2020-01-14T17:56:21Z")

</div>

Your code is too slow. Try to think: is there a way to get the sum of muffins from a to (a+K-1) in constant time if you know the sum from (a-1) to (a+K-2)?

---

<div class="post-metadata">

**Author:** ![anon28322201](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/b2d939/32.png) [@anon28322201](https://forum.olinfo.it/u/anon28322201)\
**Post date:** [19 Gennaio 2020, 11:06am UTC](https://forum.olinfo.it/t/muffin-selection-muffin-50-100/6004/3 "2020-01-19T11:06:23Z")

</div>

Intervals (a,b) and (a+1,b+1) share most of their elements, so once you’ve checked the former, do you _really_ need to iterate through the latter?