Cod sursa(job #1443233)

Utilizator lucianRRuscanu Lucian lucianR Data 27 mai 2015 11:45:29
Problema Secventa 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#define N_MAX 50000
#define INF -1000000000

using namespace std;

struct suma
{
    int s, l;
}sum[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)
    {
        s += v[i];
        if(s > s_max)
        {
            s_max = s;
            l = i - p + 1;
        }
        i++;
    }
    suma ss;
    ss.s = s_max;
    ss.l = l;
    return ss;
}

void secv()
{
    for(int i = 0; i < n; i++)
    {
        sum[i].s = INF;
    }
    int lo = 0, hi = 0, s = 0;
    for(int l = k; l < n; l++)
    {
        lo = 0, hi = l + lo, s = 0;
        for(int i = lo; i < hi; i++)
            s += v[i];
        if (s > sum[lo].s)
        {
            sum[lo].s = s;
            sum[lo].l = l;
            //cout << s << " " << l << " " << lo << endl;
        }

            //cout << s << " " << l << " " << lo << " " << v[lo-1] << " " << v[hi] << endl;
        while(hi < n)
        {
            s -= v[lo++];
            s += v[hi++];
            //cout << s << " " << l << " " << lo << " " << v[lo-1] << " " << v[hi] << endl;
            if(s > sum[lo].s)
            {
                sum[lo].s = s;
                sum[lo].l = l;
            }
        }
    }

    ofstream out("secv2.out");
    suma s_max = sum[0];
    int p = 0;
    for(int i = 0; i < n; i++)
    {
        if(sum[i].s > s_max.s)
        {
            s_max = sum[i];
            p = i;
        }
    }



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

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