Cod sursa(job #1443115)

Utilizator lucianRRuscanu Lucian lucianR Data 26 mai 2015 23:30:24
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#define N_MAX 50000

using namespace std;

struct suma
{
    int s, l;
}s[N_MAX];

int v[N_MAX], n, k;

void citire()
{
    ifstream in("secv2.in");
    in >> n >> k;
    for(int i = 0; i < n; i++)
        in >> v[i];
}

suma max_sum(int p)
{
    int i = p, s_max = 0, s = 0, l = 0;
    for(i = p; i < p + k; i++)
        s_max += v[i];
    l = i - p + 1;
    s = s_max;
    while(i < n)
    {
        //cout << v[i] << " ";
        s += v[i];
        if(s > s_max)
        {
            s_max = s;
            l = i - p + 1;
            //cout << l << endl;
        }
        i++;
    }
    suma ss;
    ss.s = s_max;
    ss.l = l;
    return ss;
}

void secv()
{
    for(int i = 0; i < n; i++)
    {
        s[i] = max_sum(i);
        /*int s = max_sum(i);
        if(s > s_max)
        {
            cout <<  endl << i << endl;
            s_max = s;
        }*/
    }
    int p = 0;
    suma s_max = s[0];
    ofstream out("secv2.out");
    for(int i = 0; i < n; i++)
    {
        if(s[i].s > s_max.s)
        {
            s_max = s[i];
            p = i;
        }
    }
    out << p+1 << " " << s_max.l + p << " " << s_max.s;
}

int main()
{
    citire();
    secv();
    return 0;
}