Pagini recente » Cod sursa (job #2097123) | Cod sursa (job #713199) | Cod sursa (job #895906) | Cod sursa (job #139020) | Cod sursa (job #1050693)
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int v[200001],s[200001],p,i,n,d,dd,pp,p2,p1,mi,mini,maxi,pl,ma,pi,pll;
int main()
{
f>>n;
for (i=1;i<=n;i++)
{
f>>v[i]>>p;
v[i + n] = v[i];
if (p==0)
v[i]= v[i+n] = -v[i];
}
int maxEndingHere = v[1];
int maxSoFar = v[1];
int begin_temp = 0, end = 0, begin = 0;
int prev_end = 0, prev_begin = 0;
int sum = v[1], currentSum = v[1], prevSum = v[1];
for (int i = 1; i <= 2 * n; i++) {
if (end - begin + 1 > n) {
begin = prev_begin;
end = prev_end;
sum = prevSum;
break;
}
// calculate max_ending_here
if (maxEndingHere < 0) {
maxEndingHere = v[i];
currentSum = v[i];
begin_temp = i;
} else {
maxEndingHere += v[i];
currentSum += v[i];
}
// calculate max_so_far
if (maxEndingHere >= maxSoFar) {
maxSoFar = maxEndingHere;
prevSum = sum;
sum = currentSum;
prev_begin = begin;
begin = begin_temp;
prev_end = end;
end = i;
}
}
if (end - begin + 1 > n) {
end = prev_end;
begin = prev_begin;
sum = prevSum;
}
g<<sum<<" "<<begin<<" "<<end - begin + 1;
f.close();
g.close();
}