Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. De exemplu, pentru șirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci șirul va deveni 3, -5, -4, 1, -6, -8, -5.
Cerința
Să se determine o pereche de indici x y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă.
Date de intrare
Fișierul de intrare sminus.in conține pe prima linie numărul N. Pe a doua linie, separate prin câte un spațiu, se găsesc numerele întregi a1, a2, …, aN.
Date de ieșire
Fișierul de ieșire sminus.out va conține două linii. Pe prima linie se vor găsi două numere naturale x și y separate printr-un spațiu reprezentând perechea de indici. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.
Restricții și precizări
2 ≤ N ≤ 100.000-1000 ≤ ai≤ 1000pentru oricei = 1..N- Secvența
ax,ax+1, …,aytrebuie să conțină cel puțin un element. - Dacă există mai multe soluții pentru perechea
(x, y), atunci se va alegea aceea care are indicelexminim, iar dacă sunt mai multe secvențe posibile care încep la pozițiax, se va alege aceea care are valoareaymaximă. - Pentru teste valorând 50 de puncte,
N ≤ 2000.
Exemplul 1:
sminus.in
7 3 -5 4 -1 6 -8 -5
sminus.out
3 5 -24
Explicație
Inversând semnul elementelor din secvența care începe la poziția 3 și se termină la poziția 5 se obține secvența
Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. De exemplu, pentru șirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci șirul va deveni 3, -5, -4, 1, -6, -8, -5.
Cerința
Să se determine o pereche de indici x y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă.
Date de intrare
Fișierul de intrare sminus.in conține pe prima linie numărul N. Pe a doua linie, separate prin câte un spațiu, se găsesc numerele întregi a1, a2, …, aN.
Date de ieșire
Fișierul de ieșire sminus.out va conține două linii. Pe prima linie se vor găsi două numere naturale x și y separate printr-un spațiu reprezentând perechea de indici. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.
Restricții și precizări
2 ≤ N ≤ 100.000-1000 ≤ ai≤ 1000pentru oricei = 1..N- Secvența
ax,ax+1, …,aytrebuie să conțină cel puțin un element. - Dacă există mai multe soluții pentru perechea
(x, y), atunci se va alegea aceea care are indicelexminim, iar dacă sunt mai multe secvențe posibile care încep la pozițiax, se va alege aceea care are valoareaymaximă. - Pentru teste valorând 50 de puncte,
N ≤ 2000.
Exemplul 1:
sminus.in
7 3 -5 4 -1 6 -8 -5
sminus.out
3 5 -24
Explicație
Inversând semnul elementelor din secvența care începe la poziția 3 și se termină la poziția 5 se obține secvența
3, -5, -4, 1, -6, -8, -5 care are suma elementelor egală cu -24.
Exemplul 2:
sminus.in
6 2 -1 2 -2 2 -6
sminus.out
1 5 -9
Explicație
Inversând semnul elementelor din secvența care începe la poziția 1 și se termină la poziția 5 se obține secvența
-2, 1, -2, 2, -2, -6 care are suma elementelor egală cu -9. Aceeași sumă minimă se putea obține și pentru perechea de indici (1, 3), dar indicele y este mai mic.
#include <bits/stdc++.h>
using namespace std;
ifstream cin("sminus.in");
ofstream cout("sminus.out");
int n, a[100001];
int main(){
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> a[i];
int smax = 0, s = 0, st = 1, dr = 1, pozi = 1, pozj = 1;
for(; dr <= n; ++dr){
s+=a[dr];
if(s < 0)
s = 0, st = dr + 1;
if(s >= smax)
smax = s, pozi = st, pozj = dr;
}
for(int i = pozi; i <= pozj; ++i)
a[i] *= -1;
int sum = 0;
for(int i = 1; i <= n; ++i)
sum+=a[i];
cout << pozi << ' ' << pozj << '\n' << sum;
return 0;
}
