Cod sursa(job #43615)

Utilizator cretuMusina Rares cretu Data 30 martie 2007 12:21:34
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#define MAX 50001

using namespace std;
int n, k;
int a[MAX];

int bit(int x);
void add(int x, int v);
int sum(int x);

int main()
{
    int i, j, smax = -32000, maxi = 0, maxj = 0, s1, s2, x;
    
    ifstream fin("secv2.in");
    fin >> n >> k;
    for (i = 1; i <= n; i++)    
    {
        fin >> x;
        add(i, x);    
    }
    fin.close();
    
    for (i = 1; i <= n-k+1; i++)
        for (j = i+k-1; j <= n; j++)
        {
            s1 = sum(i-1);
            s2 = sum(j);
            if (s2-s1 > smax)    
            {
                smax = s2-s1;
                maxi = i;
                maxj = j;    
            }
        }
    
    ofstream fout("secv2.out");
    fout << maxi << " " << maxj << " " << smax;
    fout.close();
    
    return 0;
}

void add(int x, int v)
{
    int i;
    for (i = x; i <= n; i += bit(i))    
        a[i] += v;
}

int sum(int x)
{
    int i, s = 0;
    for (i = x; i >= 1; i -= bit(i))    
        s += a[i];
    return s;
}

int bit(int x)
{
    return (x&(x-1))^x;    
}