Pagini recente » Cod sursa (job #2089159) | Cod sursa (job #1419819) | Cod sursa (job #2321412) | Cod sursa (job #956303) | Cod sursa (job #2299494)
#include <fstream>
#define DIM 200005
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
struct solutie {
int val;
int l1;
int l2;
};
int n, i, b, s, cnt, sum;
int v[DIM], t[DIM], sp[DIM], ind[DIM];
solutie sol;
int main(){
fin >> n;
for (i=1; i<=n; i++){
fin >> v[i] >> b;
if (b == 0)
v[i] = -v[i];
}
sol.val = sum = v[1];
for (i=2; i<=n; i++){ /// in cazul in care nu luam in calcul ca sirul este circular
if (sum < 0){
sum = v[i];
cnt = 1;
}
else{
sum += v[i];
cnt++;
}
if (sum > sol.val){
sol.val = sum;
sol.l1 = i - cnt + 1;
sol.l2 = i;
}
}
for (i=1; i<=n; i++){ /// daca luam sirul 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];
if (t[i-1] > sp[i]){
t[i] = t[i-1];
ind[i] = ind[i-1];
}
else{
t[i] = sp[i];
ind[i] = i;
}
}
for (i=1; i<=n; i++){
if (sol.val < t[i-1] + sp[n] - sp[i-1]){
sol.val = t[i-1] + sp[n] - sp[i-1];
sol.l1 = i;
sol.l2 = n + ind[i-1] - i + 1;
}
else{
cnt++;
}
}
fout << sol.val << " " << sol.l1 << " " << sol.l2;
return 0;
}