Pagini recente » Cod sursa (job #1972876) | Cod sursa (job #501145) | Cod sursa (job #1518535) | Cod sursa (job #2130517) | Cod sursa (job #744040)
Cod sursa(job #744040)
#include <stdio.h>
int N,*vec,*dp,i,*path,S,idx;
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&N);
vec = new int[2*N];
dp = new int[2*N];
path = new int[2*N];
for(i=0; i<N; ++i)
{
scanf("%d %d",&idx,&S);
if(S == 0)
vec[i] = -idx;
else
vec[i] = idx;
dp[i] = vec[i];
}
for(i=0;i<N;++i)
{
vec[i+N] = vec[i];
}
for(i=1; i<2*N; ++i)
{
S = dp[i-1] + vec[i];
if(S > dp[i] && path[i-1] < N)
{
dp[i] = S;
path[i] = path[i-1]+1;
}
}
S = -11111;
idx = 0;
for(i=0;i<2*N;++i)
{
if(dp[i] > S)
{
S = dp[i];
idx = i;
}
}
/*printf("Suma maxima: %d\nCu: ",S);
for(i=idx;i>0;--i)
{
printf("%d ",vec[i]);
}*/
printf("%d %d %d",S,path[idx+1], (idx+path[idx+1]-1)%N);
/*
for(i=0; i<2*N; ++i)
printf("%d ",path[i]);
*/
return 0;
}