Pagini recente » Cod sursa (job #2319803) | Cod sursa (job #2783599) | Cod sursa (job #1591026) | Cod sursa (job #1899763) | Cod sursa (job #2548399)
#include <fstream>
#define K 200002
#include <deque>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,i,c,a[K],s[2*K],p,l,smax=-2000000000;
deque <int> deq;
int main(){
fin>>n;
for(i=1;i<=n;i++){
fin>>a[i]>>c;
if(!c)a[i]*=-1;
s[i]=s[i-1]+a[i];
}
for(i=1;i<=n;i++)
s[i+n]=s[i-1+n]+a[i];
/**o secv terminata pe poz i poate incepe pe poz i-n+1,i-n+2,...i-1
sumele acestor secv sunt s[i]-s[i-n],...,s[i]-s[i-2]
ca sa fie max trb sa scad cat mai putin => deque ca sa aflu minimul*/
for(i=1;i<=2*n;i++){
while(!deq.empty() && s[i]<=s[deq.back()])
deq.pop_back();
deq.push_back(i);
if(i-deq.front()==n)
deq.pop_front();
if(s[i]-s[deq.front()]>smax){
smax=s[i]-s[deq.front()];
p=deq.front()+1;
l=i-p+1;
}
}
fout<<smax<<" "<<p<<" "<<l;
return 0;
}