Pagini recente » Cod sursa (job #2382387) | Cod sursa (job #807726) | Cod sursa (job #2578503) | Cod sursa (job #2065461) | Cod sursa (job #2488549)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n, a[400005];
struct p{
int val, start;
}dp[400005];
int x, tip;
int main()
{
f >> n;
for (int i=1; i<=n;++i)
{
f >> x >> tip;
if (tip==0)
{
a[i]=a[n+i]=-x;
}
else
{
a[i]=a[n+i]=x;
}
}
for (int i=1; i<=n; ++i)
{
dp[i].val=max(max(dp[i-1].val+a[i],a[i]),0);
if (dp[i].val==a[i])
dp[i].start=i;
else
dp[i].start=dp[i-1].start;
}
int ind=n+1;
int dublu=2*n;
while(1 && ind<=dublu)
{
dp[ind].val=max(max(dp[ind-1].val+a[ind],a[ind]),0);
if (dp[ind].val==a[ind] && dp[ind].val==0)
break;
else
dp[ind].start=dp[ind-1].start;
if (ind-dp[ind].start==n)
break;
++ind;
}
int maxi=-1, ind_start, l;
for (int i=1; i<=2*n; ++i)
{
if (dp[i].val>maxi)
{
maxi=dp[i].val;
ind_start=dp[i].start;
l=i-dp[i].start+1;
}
}
g << maxi <<' '<<ind_start <<' '<<l;
return 0;
}