Cod sursa(job #53070)

Utilizator varuvasiTofan Vasile varuvasi Data 20 aprilie 2007 20:44:38
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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];

int main()
{
    int i, 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;
    }    
    FOR (i, N+1, 2*N)
        A[i] = A[i-N];
    
    sp = 1; smax = -100044;
    FOR (i, 1, 2*N)
    {
        s += A[i];
        if (i - sp + 1 > N)
        {
            s -= A[sp];
            sp++;
        }

        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;
}