Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok
Cod sursa(job #165918)
Utilizator | Data | 27 martie 2008 09:38:43 | |
---|---|---|---|
Problema | Buline | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.72 kb |
#include <stdio.h>
#include <stdlib.h>
#define N 444111
#define Inf -2000000001
int sum,n,max=Inf,sb,lb,s,e,l;
int v[N];
void dublam()
{
for(int i=1;i<=n;++i)
v[i+n]=v[i];
}
void scan()
{
freopen("buline.in", "r",stdin);
freopen("buline.out", "w",stdout);
scanf("%d", &n);
int semn;
for(int i=1;i<=n;++i)
{
scanf("%d%d", &v[i],&semn);
if(!semn)
v[i]=-v[i];
}
}
void solve()
{
dublam();
sum=0; s=1;
for(int i=1;i<n*2 && s<n;++i)
{
if(i-s>n)
{
sum-=v[s];
++s;
}
sum+=v[i];
if(sum>max)
{
max=sum;
sb=s;
lb=i-s+1;
}
if(sum<0){
sum=0;
s=i+1;
}
}
printf("%d %d %d\n",max,sb,lb);
}
int main()
{
scan();
solve();
return 0;
}