Cod sursa(job #1729079)

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

int n,c[DIM];
ll s[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++) {
        c[i+n]=c[i];
        s[i+n]=s[i+n-1]+c[i+n];
    }
    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(i-left<l)
                    l=i-left,p=left+1;
                else if(i-left==l)
                    p=min(p,left+1);
            }
        }
    }
    fout<<maxim<<" "<<p<<" "<<l;
    return 0;
}