Cod sursa(job #1662271)

Utilizator DastasIonescu Vlad Dastas Data 24 martie 2016 17:11:21
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>

using namespace std;

#define maxn 50000

int a[maxn + 1], n, k;
int s[maxn + 1];

void read()
{
    ifstream in("secv2.in");
    in >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        in >> a[i];
        s[i + 1] = s[i] + a[i];
    }
    in.close();
}

void solve()
{
    ofstream out("secv2.out");
    // 1 << 30 inseamna 2 la puterea 30.
    int pinceput, psfarsit, maxSum = -(1 << 30);
    int pminS = 0;
    for (int i = k - 1; i < n; ++i)
    {
        //maxSum = max(maxSum, s[i] - minS);
        if (s[i + 1] - s[pminS] > maxSum)
        {
            maxSum = s[i + 1] - s[pminS];
            pinceput = pminS + 1;
            psfarsit = i + 1;
        }

        //minS = min(minS, s[i - k + 1]);
        if (s[i - k + 2] < s[pminS])
        {
            pminS = i - k + 2;
        }
    }

    out << pinceput << ' ' << psfarsit << ' ' << maxSum << endl;
}

int main()
{
    read();
    solve();

    return 0;
}