Cod sursa(job #1876151)

Utilizator valentinoMoldovan Rares valentino Data 12 februarie 2017 00:05:11
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <iostream>
#include <deque>
#define inf 0x3f3f3f3f
using namespace std;

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

int d[2] = {-1,1}, v[400010], sum, poz, len,n;
deque < int > dq;

int main()
{
    int x,y;
    f >> n;
    for(int i = 1; i <= n; ++i)
    {
        f >> y >> x;
        v[i] = y * d[x] + v[i - 1];
        v[i + n] = y * d[x];
    }
    for(int i = n + 1; i <= 2 * n ; ++i) v[i] += v[i - 1];
    sum = v[1];
    dq.push_back(1);
    for(int i = 2; i <= 2 * n; ++i)
    {
        if(i - dq.front() > n) dq.pop_front();
        if(v[i] - v[dq.front()] > sum)
        {
            sum = v[i] - v[dq.front()];
            poz = dq.front() + 1;
            len = i - dq.front();
        }
        while(!dq.empty() && v[i] < v[dq.back()]) dq.pop_back();
        dq.push_back(i);
    }
    g << sum << ' ' << poz << ' ' << len << '\n';
}