Cod sursa(job #1729082)

Utilizator liviu23Liviu Andrei liviu23 Data 14 iulie 2016 09:46:17
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <iostream>
#define DIM 200005
#define ll long long
using namespace std;

int n,c[DIM];
ll s[2*DIM];

int main()
{
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    fin>>n;
    int color;
    for(int i=1;i<=n;i++) {
        fin>>c[i]>>color;
        if(!color)
            c[i]*=-1;
        s[i]=c[i]+s[i-1];
    }
    for(int i=1;i<=n;i++)
        s[i+n]=s[i+n-1]+c[i];
    int left=0,l=1,p=1;
    ll maxim=s[1];
    for(int i=1;i<=2*n;i++) {
        if(s[i]-s[left]<=0)
            left=i;
        else {
            if(i-left-1==n)
                left++;
            if(s[i]-s[left]>maxim) {
                maxim=s[i]-s[left];
                l=i-left;
                p=left+1;
            }
            else if(s[i]-s[left]==maxim) {
                if(p>left+1)
                    p=left+1,l=i-left;
                else if(p==left+1)
                    l=min(l,i-left);
            }
        }
    }
    fout<<maxim<<" "<<p<<" "<<l;
    return 0;
}