Cod sursa(job #1522468)

Utilizator ThomasFMI Suditu Thomas Thomas Data 11 noiembrie 2015 18:59:47
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <deque>
using namespace std;

#define NMax 400005

ifstream f("buline.in");
ofstream g("buline.out");

deque<int> dq;
int sum;

int n;
int v[NMax];
int D[NMax];

int main()
{
    f>>n;

    int i, x;
    for(i=1;i<=n;++i)
    {
        f>>v[i];
        f>>x;
        if(!x) v[i] = -v[i];
        v[n+i] = v[i];
    }

    int mx = 0, poz, lung;

    int m = 2*n-1;
    for(i=1;i<=m;++i)
    {
        if(D[i-1] < 0) D[i] = v[i];
        else D[i] = D[i-1] + v[i];
        if(D[i] < 0) D[i] = 0;

        while(!dq.empty() && D[i] <= D[dq.back()]) dq.pop_back();
        dq.push_back(i);
        if(dq.front() <= i-n) dq.pop_front();

        if(D[i] - D[dq.front()] > mx)
        {
            mx = D[i] - D[dq.front()];
            poz = dq.front()+1;
            lung = i-dq.front();
        }
    }

    g<<mx<<" "<<poz<<" "<<lung<<"\n";

    f.close();
    g.close();
    return 0;
}