Cod sursa(job #843517)

Utilizator ericptsStavarache Petru Eric ericpts Data 28 decembrie 2012 00:03:43
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
using namespace std;
const int maxn = 200002;

char *p;

void read(int &a)
{
    a&=0;
    while(*p && (*p > '9' || *p < '0'))
        ++p;
    while(*p >= '0' && *p <= '9')
        a = a * 10 + *(p++)-48;
}
int v[maxn];
int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    int len;
    fseek(stdin,0,SEEK_END);
    len = ftell(stdin);
    p = new char[len];
    rewind(stdin);
    fread(p,1,len,stdin);
    int N,i;
    int semn;
    read(N);
    for(i=1;i<=N;++i)
    {
        read(v[i]);
        read(semn);
        if(!semn)
            v[i]= -v[i];
    }
    int show_sum = -(1<<30);
    int cr_sum=-(1<<30);
    int cr_pos;
    int cr_len;
    int show_pos = 0;
    int show_len = 0;
    for(i=1;i<=N;++i)
    {
        if(cr_sum > 0)
        {
            cr_sum += v[i];
            ++cr_len;
        }
        else
        {
            cr_sum = v[i];
            cr_pos = i;
            cr_len = 1;
        }
        if(cr_sum > show_sum)
        {
            show_sum = cr_sum;
            show_pos = cr_pos;
            show_len = cr_len;
        }
    }
    int last_sum=-(1<<30);
    int alt_sum=0,alt_len=0;
    for(i=1;i<show_pos;++i)
    {
        alt_sum += v[i];
        if(alt_sum > last_sum)
        {
            last_sum = alt_sum;
            alt_len = i;
        }
    }
    if(last_sum > 0)
    {
        show_sum += last_sum;
        show_len += alt_len;
    }
    printf("%d %d %d\n",show_sum,show_pos,show_len);
    return 0;
}