Cod sursa(job #2130517)

Utilizator sichetpaulSichet Paul sichetpaul Data 13 februarie 2018 18:46:11
Problema Buline Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <deque>
using namespace std;
deque <int> Min;
int s[200001],v[200001];
int main()
{ int n,i,poz,lun,Max=0,tip;
    ifstream f("buline.in");
    ofstream g("buline.out");
    f>>n;
    for (i=1;i<=n;++i) {
        f>>v[i]>>tip;
        if (tip==0) v[i]*=-1;
        s[i]=s[i-1]+v[i];
    }
    for (i=n+1;i<=2*n;++i)
        s[i]=s[i-1]+v[i-n];
    Max=-n*10000;
    for (i=1;i<=2*n;++i) {
        while (!Min.empty() && s[i]<s[Min.back()])
            Min.pop_back();
        Min.push_back(i);
        if (i>=n) {
            if (s[i]-s[Min.front()]>Max) {
                Max=s[i]-s[Min.front()];
                poz=Min.front()+1;
                lun=i-Min.front();
            }
            if (Min.front()==i-n+1) Min.pop_front();
        }
    }
      g<<Max<<" "<<poz<<" "<<lun;
    return 0;
}