Cod sursa(job #1180653)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 30 aprilie 2014 20:54:54
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <deque>
using namespace std;
deque <int> dq;
int v[400040];
int s[400040];

int main()
{
    ifstream in("buline.in");
    ofstream out("buline.out");
    int n, bul, semn, smax = -10000, p, l;
    in >> n;
    for(int i = 1; i <= n; ++i) {
         in >> bul >> semn;
         if(semn == 0) v[i + n] = v[i] = -bul;
         else v[i + n] = v[i] = bul;
         s[i] = s[i - 1] + v[i];
    }
    for(int i = n + 1; i <= 2*n; ++i)
      s[i] = s[i - 1] + v[i];
    for(int i = 1; i <= 2*n; ++i)
    {
        while(!dq.empty() && s[i] <= s[dq.back()])
            dq.pop_back();
        dq.push_back(i);
        if(dq.front() == i - n)
            dq.pop_front();
        if(smax < s[i] - s[dq.front()]) {
            smax = s[i] - s[dq.front()];
            p = dq.front() + 1;
            l = i - p +1;
        }
    }
    out << smax << " " << p << " " << l;
    return 0;
}