Cod sursa(job #1479979)

Utilizator CalinCojoFMI Cojocaru Calin George CalinCojo Data 1 septembrie 2015 19:41:35
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("ssm.in",ios::in);
ofstream g("ssm.out",ios::out);

int sum[7000001],n,k;
void ssm()
{
    f>>n;
    for(int i = 0 ; i < n ;i++)
        f>>sum[i];

    //obs : folosesc acelasi vector deoarece in caz contrat as folosi prea multa memorie
    int minSum = 0 ,maxSum = -2000000 ,lIndex = 1,rIndex = 1 ,auxSum,aux_lIndex = 1;

    for (int i = 1 ; i < n ; i++)
    {
        // actualizez daca e cazul minSum comparandu-l cu sum[i-1]
        if(sum[i-1] < minSum)
        {
            minSum = sum[i-1];
            aux_lIndex = i+1;
        }
        //creez sum[i]
        sum[i] = sum[i-1] + sum[i];
        // vad ce subsir care se termina in i are suma maxima
        auxSum = sum[i] - minSum;
        // compar subsirul cu maxSum, actualizand indicii
        if(auxSum > maxSum)
        {
            maxSum = auxSum;
            rIndex = i + 1;
            lIndex = aux_lIndex;
        }
    }
    //cout<<maxSum<<" "<<lIndex<<" "<<rIndex;
    g<<maxSum<<" "<<lIndex<<" "<<rIndex;
}

void ssm_optimizat()
{
    //variabile
    int minSum = 0 ,maxSum = -2000000 ,lIndex = 1,rIndex = 1, aux_lIndex = 1,curSum,prevSum;
    f>>n>>k;
    f>>prevSum;
    for(int i = 1 ; i < n ; i++)
    {
        f>>curSum;
        curSum+=prevSum;
        //verific daca subsirul de dinainte are suma minima
        if(prevSum < minSum)
        {
            minSum = prevSum;
            aux_lIndex = i+1;
        }
        //verific daca subsirul de suma maxima care se termina pe poz i este subsir de suma max
        if(maxSum < curSum - minSum)
        {
            if(i+1 - aux_lIndex > k)
            {
                maxSum = curSum - minSum;
                rIndex = i + 1;
                lIndex = aux_lIndex;
            }
        }
        //curSum devine prevSum pt iteratia urmatoare
        prevSum = curSum;
    }
    //cout<<maxSum<<" "<<lIndex<<" "<<rIndex;
    g<<maxSum<<" "<<lIndex<<" "<<rIndex;
}
int main()
{
    //ssm();
    ssm_optimizat();
    f.close();
    g.close();
}