Cod sursa(job #1729215)

Utilizator liviu23Liviu Andrei liviu23 Data 14 iulie 2016 13:54:57
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 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(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);
        }
        while(left<i&&s[i]<s[left])
            left++;
    }
    fout<<maxim<<" "<<p<<" "<<l;
    return 0;
}