Cod sursa(job #1829209)

Utilizator EpictetStamatin Cristian Epictet Data 14 decembrie 2016 16:20:37
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <queue>

using namespace std;

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

int n, best_sum, best_sum_pos, best_sum_lg, SUM[400010];
deque < int > DQ;

int main()
{
    fin >> n;
    for (int aa, av, i = 1; i <= n; i ++)
    {
        fin >> av >> aa;
        if (!aa) av = -av;
        SUM[i] = SUM[i - 1] + av;
        SUM[i + n] = av;
    }
    for (int i = n + 1; i <= n * 2; i ++) SUM[i] += SUM[i - 1];

    best_sum = SUM[1];
    DQ.push_back(1);
    for (int i = 2; i <= n * 2; i ++)
    {
        if (i - DQ.front() > n) DQ.pop_front();
        if (SUM[i] - SUM[DQ.front()] > best_sum)
        {
            best_sum = SUM[i] - SUM[DQ.front()];
            best_sum_pos = DQ.front() + 1;
            best_sum_lg = i - DQ.front();
        }
        while (!DQ.empty() && SUM[i] < SUM[DQ.back()]) DQ.pop_back();
        DQ.push_back(i);
    }

    fout << best_sum << ' ' << best_sum_pos<< ' ' << best_sum_lg << '\n';
    fout.close();
    return 0;
}