Pagini recente » Cod sursa (job #379369) | Cod sursa (job #2299473)
#include <fstream>
#define DIM 200005
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
struct solutie {
int val;
int l1;
int l2;
};
long long n, i, b, s, cnt;
long long v[DIM], t[DIM], sp[DIM];
solutie sol1, sol2, ssm;
int main()
{
fin >> n;
for (i=1; i<=n; i++){
fin >> v[i] >> b;
if (b == 0)
v[i] = -v[i];
}
for (i=1; i<=n; i++){ /// in cazul in care nu luam in calcul ca sirul este circular
s = max (s + v[i], v[i]);
if (sol1.val < s){
sol1.val = s;
sol1.l2 = i;
sol1.l1 = i - cnt + 1;
}
else{
cnt++;
}
}
for (i=1; i<=n; i++){ /// in cazul in care iau in calcul ca sirul este circular, calculez cea mai buna secventa de tipul i, i+1, ..., n-1, n, 1, 2, ..., j-1, j
sp[i] = sp[i-1] + v[i];
t[i] = max (t[i-1], sp[i]);
}
cnt = 0;
for (i=1; i<=n; i++){
if (sol2.val < t[i-1] + sp[n] - sp[i-1]){
sol2.val = t[i-1] + sp[n] - sp[i-1];
sol2.l2 = i;
sol2.l1 = i - cnt + 1;
}
else{
cnt++;
}
}
ssm = ((sol1.val > sol2.val) ? sol1 : sol2);
fout << ssm.val << " " << ssm.l1 << " " << ssm.l2;
return 0;
}