Pagini recente » Cod sursa (job #3252833) | Cod sursa (job #468643) | Cod sursa (job #1972787) | Cod sursa (job #3144001) | Cod sursa (job #27607)
Cod sursa(job #27607)
#include <stdio.h>
#include <deque>
using namespace std;
#define infile "buline.in"
#define outfile "buline.out"
#define INF 2000000005
#define NMAX 200005
FILE *fin,*fout;
int n,X[2*NMAX];
int sumamax=-INF,pozmin,L;
deque<int> D;
int S[2*NMAX];
void citire()
{
int i,cul;
fin=fopen(infile,"r");
fscanf(fin,"%d",&n);
X[0]=0;
for(i=1;i<=n;i++)
{
fscanf(fin,"%d %d",&X[i],&cul);
if(!cul)
X[i]=-X[i];
}
for(i=n+1;i<=2*n;i++)
X[i]=X[i-n];
fclose(fin);
}
inline void adauga_deque(int x)
{
while(!D.empty() && S[D.back()]>S[x])
D.pop_back();
D.push_back(x);
}
inline void sterge_deque(int x)
{
if(D.empty())
return;
if(D.front()==x)
D.pop_front();
}
inline int min_deque()
{
return D.front();
}
void solve()
{
int i,poz,change;
S[0]=0;
adauga_deque(0);
for(i=1;i<=2*n;i++)
{
S[i]=S[i-1]+X[i];
sterge_deque(i-n-1);
poz=min_deque();
change=0;
if(sumamax<S[i]-S[poz])
change=1;
else
if(sumamax==S[i]-S[poz])
if(poz<pozmin)
change=1;
else
if(poz==pozmin && L>i-poz)
change=1;
if(change)
{
sumamax=S[i]-S[poz];
pozmin=poz;
L=i-poz;
}
adauga_deque(i);
}
}
int main()
{
citire();
solve();
fout=fopen(outfile,"w");
fprintf(fout,"%d %d %d\n",sumamax,pozmin+1,L);
fclose(fout);
return 0;
}