Cod sursa(job #1522448)

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

#define NMax 10005

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

deque<int> dq;
int sum;

int n;
int v[NMax + 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;
    for(i=1;i<=m;++i)
    {
        if(sum <= 0)
        {
            dq.clear();
            dq.push_back(i);
            sum = v[i];
        }
        else
        {
            dq.push_back(i);
            sum += v[i];
        }
        if(!dq.empty() && dq.front() <= i-n)
        {
            sum -= v[dq.front()];
            dq.pop_front();
        }
        while(!dq.empty() && v[dq.front()] < 0)
        {
            sum -= v[dq.front()];
            dq.pop_front();
        }

        if(sum > mx)
        {
            mx = sum;
            poz = dq.front();
            lung = dq.size();
        }
    }

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

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