Pagini recente » Cod sursa (job #2706327) | Cod sursa (job #3177144) | Cod sursa (job #2369279) | Cod sursa (job #419686) | Cod sursa (job #3268264)
#include <bits/stdc++.h>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
const int INF = INT_MAX;
const int MAX_N = 200'000;
int v[MAX_N + 1], n;
long long sMax, pMax, lMax;
long long sMin, pMin, lMin;
long long s, p, l;
long long S;
bool flag;
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> v[i] >> flag;
if (!flag)
v[i] = -v[i];
S += v[i];
}
///for (int i = 1; i <= n; i++)
/// cout << v[i] << ' ';
///cout << '\n';
sMax = -INF;
/// Cazul 1. Subsecventa de suma maxima este intre 1 si n
s = sMax = v[1];
l = lMax = 1;
p = pMax = 1;
for (int i = 2; i <= n; i++)
{
/// s = max(s + v[i], v[i]);
if (s + v[i] > v[i]) /// if (s > 0)
{
s = s + v[i];
l++;
}
else
{
s = v[i];
p = i;
l = 1;
}
if (s > sMax)
{
sMax = s;
pMax = p;
lMax = l;
}
}
/// Cazul 2. Subsecventa de suma maxima incepe pe la sfarsitul sirului si se termina spre mijloc
/// s = S - (v[l] + ... + v[r]) - maxima, deci (v[l] + ... + v[r]) - minima
s = sMin = v[1];
l = lMin = 1;
p = pMin = 1;
for (int i = 2; i <= n; i++)
{
/// s = min(v[i], s + v[i]);
if (s + v[i] < v[i]) /// if (s > 0)
{
s = s + v[i];
l++;
}
else
{
s = v[i];
p = i;
l = 1;
}
if (s < sMin)
{
sMin = s;
pMin = p;
lMin = l;
}
}
s = S - sMin;
if (s > sMax)
{
sMax = s;
pMax = pMin + lMin;
lMax = n - lMin;
}
g << sMax << ' ' << pMax << ' ' << lMax << '\n';
f.close();
g.close();
return 0;
}