Cod sursa(job #1747530)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 25 august 2016 02:56:57
Problema Buline Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out");
const int maxn = 400005;
deque <int> dq;
int sp[maxn];
int v[maxn];
int main()
{
    int n;
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        int aux;
        in >> v[i] >> aux;
        if(aux == 0)
            v[i] = -v[i];
        v[i + n] = v[i];
    }
    for(int i = 1; i <= n * 2; i++)
        sp[i] = sp[i - 1] + v[i];
    for(int i = 1; i < n; i++)
    {
        while(!dq.empty() && v[dq.back()] >= v[i])
            dq.pop_back();
        dq.push_back(i);
    }
    int mx = 0;
    int st = 0;
    int lg = 0;
    for(int i = n; i <= n * 2 - 1; i++)
    {
        while(!dq.empty() && sp[dq.back()] >= sp[i])
            dq.pop_back();
        dq.push_back(i);
        if(dq.front() <= i - n + 1)
            dq.pop_front();
        if(mx < sp[i + 1] - sp[dq.front()])
        {
            mx = sp[i + 1] - sp[dq.front()];
            st = dq.front() + 1;
            lg = i - dq.front() + 1;
        }
    }
    out << mx << " " << st << " " << lg << "\n";
    return 0;
}