Cod sursa(job #353269)

Utilizator aladinaladin aladinn aladin Data 4 octombrie 2009 15:57:14
Problema Buline Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
#include <deque>
using namespace std;

deque <int> ss;

int main()
{int n,i,v[40009],max,st,l;

 freopen("buline.in","r",stdin);
 freopen("buline.out","w",stdout);
 scanf("%d",&n);
 for (i=1;i<=n;++i) 
 {scanf("%d %d",&st,&l); if (l==0) v[i]=v[i-1]-st; else v[i]=v[i-1]+st;}
 for (i=n+1;i<2*n;++i) 
	 v[i]=v[n]+v[i-n];
 for (i=2;i<=n;++i) 
 {while (!ss.empty()&&v[ss.back()]<v[i]) ss.pop_back();
  ss.push_back(i);
 }
 max=v[ss.front()],st=1,l=ss.front();
 for (i=1;i<=n;++i)
 {if (v[ss.front()]-v[i-1]>max) max=v[ss.front()]-v[i-1],st=i,l=ss.front()-i+1; 
  if (ss.front()==i+1) ss.pop_front();
  while (!ss.empty()&&v[ss.back()]<v[n+i]) 
	  ss.pop_back();
  ss.push_back(n+i);
 }
 printf("%d %d %d",max,st,l);
 return 0;}