Pagini recente » Cod sursa (job #1524527) | Cod sursa (job #1579865) | Cod sursa (job #2062371) | Cod sursa (job #2482477) | Cod sursa (job #2488572)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n, a[400005], s;
deque<int>deck;
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)
{
s+=a[i];
if (s<=0)
{
while (!deck.empty())
{
s-=a[deck.front()];
deck.pop_front();
}
s=0;
}
else
{
deck.push_back(i);
dp[i].start=deck.front();
}
dp[i].val=s;
}
int dublu=2*n;
for (int i=n+1; i<=dublu; ++i)
{
s+=a[i];
if (s<=0)
{
while (!deck.empty())
{
s-=a[deck.front()];
deck.pop_front();
}
s=0;
}
else
{
deck.push_back(i);
while (deck.back()-deck.front()+1>n)
{
s-=a[deck.front()];
deck.pop_front();
}
dp[i].start=deck.front();
}
dp[i].val=s;
}
int maxi=-1, l, poz;
for (int i=1; i<=dublu; ++i)
{
if (dp[i].val>maxi)
{
maxi=dp[i].val;
poz=dp[i].start;
l=i-dp[i].start+1;
}
else if (dp[i].val==maxi)
{
if (dp[i].start<l)
{
poz=dp[i].start;
l=i-dp[i].start+1;
}
else if (i-dp[i].start+1<l)
{
poz=dp[i].start;
l=i-dp[i].start+1;
}
}
}
g << maxi <<' '<<poz <<' '<<l;
return 0;
}