Pagini recente » Cod sursa (job #2845338) | Cod sursa (job #490453)
Cod sursa(job #490453)
/*
* File: main.cpp
* Author: petru
*
* Created on 2010-10-06
*/
#include <fstream>
#include <deque>
#define deb(n) fprintf(stderr,"%d ",(n));
#define DN 200005
#define MULT 0x3f3f3f3f
#define LL long long
//#define int long long
using namespace std;
LL sir[DN*2],sol,st,lg;
int n;
int main()
{
int i;
ifstream f("buline.in");
ofstream g("buline.out");
f>>n;
for(i=1; i<=n; ++i) {
int op;
f>>sir[i]>>op;
if(!op) sir[i]*=(-1);
}
for(i=n+1;i<n*2; ++i) sir[i]=sir[i-n];
//n*=2;
for(i=1;i<n*2; ++i) sir[i]+=sir[i-1];
deque <int> d;
for(i=1; i<n*2; ++i) {
for(;!d.empty() && d.front()<=i-n;d.pop_front());
for(;!d.empty() && sir[i]<sir[d.back()];d.pop_back());
d.push_back(i);
if(sir[i]-sir[d.front()]>sol) {
sol=sir[i]-sir[d.front()];
st=d.front()+1;
lg=i-d.front();
}
}
g<<sol<<' '<<st<<' '<<lg;
f.close();
g.close();
return 0;
}