Pagini recente » Cod sursa (job #1248854) | Cod sursa (job #3283912)
#include <fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n;
int v[200001];
bool albnegru;
int s[200001];
int st[200001],l[200001];
int stmax,lmax;
int maxi;
int smin[200001];
int mini;
int drmini;
int lmini;
int lmin[200001];
int suma;
int main()
{
fin >> n;
for(int i=1; i<=n; i++){
fin >> v[i] >> albnegru;
if(albnegru == 0) v[i] = -v[i];
suma += v[i];
}
s[1] = v[1];
st[1] = 1;
for(int i=2; i<=n; i++){
if(s[i-1] + v[i] >= v[i]){
s[i] = s[i-1] + v[i];
st[i] = st[i-1];
l[i] = l[i-1] + 1;
}
else{
s[i] = v[i];
st[i] = i;
l[i] = 1;
}
}
maxi = -1e9-7;
for(int i=1; i<=n; i++){
if(s[i] > maxi){
maxi = s[i];
stmax = st[i];
lmax = l[i];
}
}
smin[2] = v[2];
for(int i=3; i<n; i++){
if(smin[i-1] + v[i] <= v[i]){
smin[1] = smin[i-1] + v[i];
lmin[i] = lmin[i-1]++;
}
else{
smin[i] = v[i];
lmin[i] = 1;
}
drmini = i;
}
mini = 1e9+7;
for(int i=2; i<n; i++){
if(smin[i] < mini){
mini = smin[i];
lmini = lmin[i];
drmini = i + 1;
}
}
if(suma - mini > maxi){
maxi = suma - mini;
fout << maxi << " " << drmini << " " << n - lmini + 1;
}
else{
fout << maxi << " " << stmax << " " << lmax;
}
return 0;
}