Pagini recente » Cod sursa (job #2136516) | Cod sursa (job #1763015) | Cod sursa (job #2855072) | Cod sursa (job #2713155) | Cod sursa (job #1729227)
#include <deque>
#include <fstream>
#define DIM 200005
#define ll long long
using namespace std;
deque<int> d;
int n,c[DIM];
ll s[2*DIM];
int main()
{
ifstream fin("buline.in");
ofstream fout("buline.out");
fin>>n;
int color;
for(int i=1;i<=n;i++) {
fin>>c[i]>>color;
if(!color)
c[i]*=-1;
s[i]=c[i]+s[i-1];
}
for(int i=1;i<=n;i++)
s[i+n]=s[i+n-1]+c[i];
int left=0,l=1,p=1;
ll maxim=s[1];
for(int i=1;i<=2*n;i++) {
while(!d.empty()&&s[i]<=s[d.back()])
d.pop_back();
d.push_back(i);
if(d.front()==i-n)
d.pop_front();
if(maxim<s[i]-s[d.front()]) {
maxim=s[i]-s[d.front()];
p=d.front()+1;
l=i-d.front();
}
}
fout<<maxim<<" "<<p<<" "<<l;
return 0;
}