Cod sursa(job #2548399)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 16 februarie 2020 16:54:09
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#define K 200002
#include <deque>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,i,c,a[K],s[2*K],p,l,smax=-2000000000;
deque <int> deq;
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>a[i]>>c;
        if(!c)a[i]*=-1;
        s[i]=s[i-1]+a[i];
    }
    for(i=1;i<=n;i++)
        s[i+n]=s[i-1+n]+a[i];
/**o secv terminata pe poz i poate incepe pe poz i-n+1,i-n+2,...i-1
 sumele acestor secv sunt s[i]-s[i-n],...,s[i]-s[i-2]
 ca sa fie max trb sa scad cat mai putin => deque ca sa aflu minimul*/
    for(i=1;i<=2*n;i++){
        while(!deq.empty() && s[i]<=s[deq.back()])
            deq.pop_back();
        deq.push_back(i);
        if(i-deq.front()==n)
            deq.pop_front();
        if(s[i]-s[deq.front()]>smax){
            smax=s[i]-s[deq.front()];
            p=deq.front()+1;
            l=i-p+1;
        }
    }
    fout<<smax<<" "<<p<<" "<<l;
    return 0;
}