Cod sursa(job #27557)

Utilizator mariusdrgdragus marius mariusdrg Data 6 martie 2007 15:17:27
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>

const int maxn = 200000;

int i;
int n;
int maxi;
int st;
int le;
int t[maxn];
int x;
int s[maxn];
int a[maxn];
int pozs[maxn];

int main()
{
        freopen("buline.in","r",stdin);
        freopen("buline.out","w",stdout);
        scanf("%d",&n);
        for(i = 1;i <= n;++i)
        {
                scanf("%d %d",&a[i],&x);
                if (x == 0) a[i] *= -1;
        }
        for(i = 1;i <= n; ++i)
        {
                s[i] = s[i - 1] + a[i];
                if (t[i - 1]> s[i] )
                {
                        t[i] = t[i-1];
                        pozs[i]= pozs[i - 1];
                }
                else
                {
                        t[i] = s[i];
                        pozs[i] = i;
                }
        }
        for(i = 1;i <= n; ++i)
        {
                int sol = s[n] - s[i - 1] + t[i - 1];
                if (maxi < sol)
                {
                        maxi = sol;
                        st = i;
                        le = pozs[i - 1] + n - i + 1;
                }
        }
        printf("%d %d %d",maxi,st,le);
        printf("\n");
        return 0;
}