Pagini recente » Istoria paginii utilizator/[email protected] | Cod sursa (job #641916) | Cod sursa (job #3303587) | Cod sursa (job #2044155) | Cod sursa (job #3347532)
#include <fstream>
using namespace std;
ifstream cin("buline.in");
ofstream cout("buline.out");
long long v[400005];
long long s[400005];
int deq[400005];
int main() {
int n;
cin >> n;
for (int i=1; i<=n; i++) {
int va, c;
cin>>va>>c;
if (c==0)
v[i]=-va;
else
v[i]=va;
v[i+n]=v[i];
}
for (int i=1; i<=2*n; i++) {
s[i]=s[i-1]+v[i];
}
long long vmax=-2e18;
int startb=1, lmax=1;
int f=0, c=0;
deq[c++]=0;
for (int i=1; i<2*n; i++) {
while (f<c&&deq[f]<i-n) {
f++;
}
long long sum=s[i]-s[deq[f]];
int l=i-deq[f];
int start=(deq[f]+1>n) ? deq[f] + 1 - n : deq[f] + 1;
if (sum>vmax) {
vmax=sum;
startb=start;
lmax=l;
} else if (sum==vmax) {
if (start<startb) {
startb=start;
lmax=l;
}
else if (start==startb && l<lmax) {
lmax=l;
}
}
while (f<c&&s[deq[c-1]]>=s[i]) {
c--;
}
deq[c++]=i;
}
cout<<vmax<<" "<<startb<<" "<<lmax<<"\n";
return 0;
}