Pagini recente » Diferente pentru problema/arbset intre reviziile 3 si 4 | Cod sursa (job #630374) | Diferente pentru problema/joc8 intre reviziile 8 si 3 | Cod sursa (job #1131758) | Cod sursa (job #3346180)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream in("buline.in");
ofstream out("buline.out");
int n;
in >> n;
vector<long long> a(n+1);
long long total = 0;
for(int i=1;i<=n;i++)
{
long long x;
int c;
in >> x >> c;
if(c==0) x = -x;
a[i] = x;
total += x;
}
long long s=0, bestMax=-1e18;
int st=1, bestL=1, bestR=1;
for(int i=1;i<=n;i++)
{
if(s<0)
{
s=a[i];
st=i;
}
else
s+=a[i];
if(s>bestMax || (s==bestMax && (st<bestL || (st==bestL && i-st<bestR-bestL))))
{
bestMax=s;
bestL=st;
bestR=i;
}
}
s=0;
long long bestMin=1e18;
st=1;
int minL=1,minR=1;
for(int i=1;i<=n;i++)
{
if(s>0)
{
s=a[i];
st=i;
}
else
s+=a[i];
if(s<bestMin)
{
bestMin=s;
minL=st;
minR=i;
}
}
long long circular = total - bestMin;
if(minL==1 && minR==n) circular = -1e18;
if(bestMax >= circular)
{
out << bestMax << " " << bestL << " " << bestR-bestL+1;
}
else
{
int start = minR+1;
if(start>n) start=1;
int len = n - (minR-minL+1);
out << circular << " " << start << " " << len;
}
}