Pagini recente » Cod sursa (job #2850641) | Cod sursa (job #2162723) | Cod sursa (job #2162311) | Cod sursa (job #3245388) | Cod sursa (job #3275267)
#include <bits/stdc++.h>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n, v[200005], smax = INT_MIN, smin = INT_MAX, s, sum, st_max, dr_max, st, st_min, dr_min;
bool t;
int main(void)
{
f >> n;
for (int i = 1; i <= n; i++) {
f >> v[i] >> t;
if (!t) {
v[i] *= (-1); // valori negative pentru bile negre
}
sum += v[i]; // calculez suma totala
}
// PENTRU SUMA MAXIMA
s = v[1]; // initializez suma curenta
st_max = dr_max = st = 1; // pozitia secventei maxime
for (int i = 2; i <= n; i++) {
if (s + v[i] >= v[i]) { // extind secventa curenta
s += v[i];
} else { // incep o noua secventa
s = v[i];
st = i;
}
if (s > smax) { // actualizez suma maxima
smax = s;
st_max = st;
dr_max = i;
}
}
// PENTRU SUMA MINIMA PENTRU CAZUL CIRCULAR
// analog ca la suma maxima
s = v[1]; // initializez suma curenta
st_min = dr_min = st = 1; // pozitia secventei minime
for (int i = 2; i <= n; i++) {
if (s + v[i] <= v[i]) { // extind secventa curenta
s += v[i];
} else { // incep o noua secventa
s = v[i];
st = i;
}
if (s < smin) { // actualizez suma minima
smin = s;
st_min = st;
dr_min = i;
}
}
// comparam suma maxima obtinuta cu cea care trece circular
if (smax > sum - smin)
g << smax << " " << st_max << dr_max - st_max + 1;
else
// *Calculăm corect poziția secvenței în cazul circular*
// dr_min + 1 este prima poziție după secvența minimă
// st_min - 1 este ultima poziție înainte de secvența minimă
// n - dr_min reprezintă lungimea bucății rămase după eliminarea secvenței minime
g << sum - smin << " " << dr_min + 1 << st_min - 1 + n - dr_min;
return 0;
}