Cod sursa(job #53223)

Utilizator varuvasiTofan Vasile varuvasi Data 21 aprilie 2007 15:34:12
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#define FOR(i, a, b) for (i = (a); i <= (b); i++)
#define FORD(i, a, b) for (i = (a); i >= (b); i--)

#define MaxN 400044

int N;
int A[MaxN], spart[MaxN], prec[MaxN]. q[MaxN];

void ins(int pos, int sp)
{
    if (!head) q[++head] = pos, tail = head;
    else
    {
        while (head <= tail && (spart[q[tail]] - spart[sp - 1]) > (spart[pos] - spart[sp - 1])]) tail--;
        q[++tail] = pos;
    }
    if (pos - sp + 1 > N) head++;
}

int main()
{
    int i, j, val, sgn, sp, smax = 0, s = 0, spsol, lsol;
    
    FILE *fin = fopen("buline.in", "rt");
    FILE *fout = fopen("buline.out", "wt");
    
    fscanf(fin, "%d", &N);
    FOR (i, 1, N)    
    {   
        fscanf(fin, "%d %d", &val, &sgn);
        if (!sgn) val *= -1;
        A[i] = val;
        spart[i] = spart[i-1] + A[i];
    }    
    FOR (i, N+1, 2*N)
    {
        A[i] = A[i-N];
        spart[i] = spart[i-1] + A[i];
    }    

	sp = 1; smax = -100044;
	FOR (i, 1, 2*N)
	{
		s += A[i];
		if (i - sp + 1 > N)
		{
			s -= A[sp];
			sp++;

			int sum = s, pos = sp;

			FOR(j, sp, i)
				if (spart[i] - spart[j - 1] > sum)
					sum = (spart[i] - spart[j - 1]), pos = j;
			s = sum;
			sp = pos;
		}

		if (s > smax)
		{
			smax = s;
			spsol = sp;
			lsol = i - sp + 1;
		}

		if (s < 0)
		{
			sp = i+1;
			s = 0;
		}
	}

	fprintf(fout, "%d %d %d\n", smax, spsol, lsol);

	/*FOR (i, 1, 2*N)
        fprintf(fout, "%d ", A[i]);*/
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}