Pagini recente » Cod sursa (job #3203574) | Cod sursa (job #2281325) | Cod sursa (job #1557933) | Cod sursa (job #865110) | Cod sursa (job #3261487)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 2e5 + 1;
int N, sum;
int v[N_MAX];
tuple<int, int, int> ans;
void SetInput(string name)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
(void)!freopen((name + ".in").c_str(), "r", stdin);
(void)!freopen((name + ".out").c_str(), "w", stdout);
}
void ReadArray()
{
cin >> N;
sum = 0;
for(int i = 1, t; i <= N; i++)
{
cin >> v[i] >> t;
if(t == 0)
v[i] = -v[i];
sum += v[i];
}
}
void CompareToAns(tuple<int, int, int>& t)
{
if(get<0>(ans) < get<0>(t))
ans = t;
else if(get<0>(ans) == get<0>(t))
{
if(get<1>(ans) > get<1>(t))
ans = t;
else if(get<1>(ans) == get<1>(t) && get<2>(ans) > get<2>(t))
ans = t;
}
}
void Solve()
{
pair<int, int> ssMin, ssMax;
tuple<int, int, int> temp;
ssMin = ssMax = make_pair(v[1], 1);
ans = make_tuple(ssMax.first, 1, 1);
temp = make_tuple(sum - ssMin.first, 2, N-1);
CompareToAns(temp);
for(int i = 2; i <= N; i++)
{
/// Find ssMax
if(ssMax.first < 0)
ssMax = make_pair(v[i], i);
else
ssMax.first += v[i];
temp = make_tuple(ssMax.first, ssMax.second, i - ssMax.second + 1);
CompareToAns(temp);
/// Find ssMin
if(ssMin.first > 0)
ssMin = make_pair(v[i], i);
else
ssMin.first += v[i];
temp = make_tuple(sum - ssMin.first, i + 1, N - (i - ssMin.second + 1)); /// Can have N + 1 (for i = N) since it is at most worse than sum of first N nums
CompareToAns(temp);
}
cout << get<0>(ans) << ' ' << get<1>(ans) << ' ' << get<2>(ans) << '\n';
}
int main()
{
SetInput("buline");
ReadArray();
Solve();
return 0;
}