Cod sursa(job #1496525)

Utilizator EpictetStamatin Cristian Epictet Data 5 octombrie 2015 08:53:49
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin ("buline.in");
ofstream fout ("buline.out");

int n, poz, lg, V[400010];
bool value;
deque < int > DQ;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> V[i] >> value;
        if (value == 0) V[i] *= (-1);
    }
    for (int i = n + 1; i < n + n; i++)
    {
        V[i] = V[i - n];
    }

    long long s = 0, sum = -1000000;
    for (int i = 1; i < n + n; i++)
    {
        if (DQ.size() == n)
        {
            s -= V[DQ.front()];
            DQ.pop_front();
        }
        if (s < 0)
        {
            s = V[i];
            DQ.clear();
            DQ.push_back(i);
        }
        else
        {
            DQ.push_back(i);
            s += V[i];
        }
        if (s > sum)
        {
            sum = s;
            poz = DQ.front();
            lg = DQ.size();
        }
    }

    fout << sum << ' ' << poz << ' ' << lg << '\n';
    fout.close();
    return 0;
}