Pagini recente » Cod sursa (job #1198882) | Cod sursa (job #226911) | Cod sursa (job #2092635) | Cod sursa (job #2934959) | Cod sursa (job #1496478)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n;
vector<int> v(n);
struct AA
{
int start, stop, max;
};
AA f()
{
int start = 0;
int stop = 0;
int sum = 0;
int max = -2000000000;
int max_start = 0;
int max_stop = 0;
for(int i=0;i<n;i++)
{
if(sum>=0)
{
sum += v[i];
stop = i;
}
else
{
start=stop=i;
sum = v[i];
}
if(sum>max)
{
max=sum;
max_start = start;
max_stop = stop;
}
}
AA aa = {max_start, max_stop, max};
return aa;
}
AA g()
{
int start = 0;
int stop = 0;
int sum = 0;
int max = 2000000000;
int max_start = 0;
int max_stop = 0;
for(int i=0;i<n;i++)
{
if(sum<=0)
{
sum += v[i];
stop = i;
}
else
{
start=stop=i;
sum = v[i];
}
if(sum<max)
{
max=sum;
max_start = start;
max_stop = stop;
}
}
AA aa = {max_start, max_stop, max};
return aa;
}
int main ()
{
ifstream fin("buline.in");
ofstream fout("buline.out");
fin>>n;
v.resize(n);
int x,y;
int total_sum = 0;
for(int i=0;i<n;i++)
{
fin>>x>>y;
v[i] = y?x:-x;
total_sum+=v[i];
}
AA aa = f();
AA bb = g();
//cout<<total_sum<<endl;
//cout<<aa.max<<" "<<bb.max<<endl;
if(aa.max>=total_sum-bb.max)
{
// cout<<"AA";
fout<<aa.max<<" "<<aa.start+1<<" "<<aa.stop-aa.start+1;
}
else
{
// cout<<"BB"<<" "<<bb.stop<<" "<<bb.start<<endl;
fout<<total_sum-bb.max<<" "<<(bb.stop+1)%n+1<<" "<<n-(bb.stop-bb.start)-1;
}
return 0;
}