Cod sursa(job #1729070)

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

int n,c[DIM];
ll s[DIM];
deque<int> q;

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,maxim=s[1],l=1,p=1;
    for(int i=1;i<=2*n;i++) {
        if(s[i]-s[left]<=0) {
            while(left<i)
                q.pop_back(),left++;
        }
        else {
            q.push_front(i);
            if(i-left>n)
                left++,q.pop_back();
            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=left+1;
            }
        }
    }
    fout<<maxim<<" "<<p<<" "<<l;
    return 0;
}