Pagini recente » Cod sursa (job #93111) | Cod sursa (job #2903509) | Cod sursa (job #2128116) | Cod sursa (job #1637816) | Cod sursa (job #3264058)
#include <bits/stdc++.h>
using namespace std;
/**
dp[i] - secventa de suma minima care se termina in i
*/
const int MAX = 6000005;
int a[MAX], dp[MAX];
int main()
{
ifstream cin("buline.in");
ofstream cout("buline.out");
int n, total = 0, minim = INT_MAX, st = 0, ans_left = 0, ans_right = 0;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int x, c;
cin >> x >> c;
a[i] = (c == 0) ? -x : x;
total += a[i];
}
dp[1] = a[1];
for (int i = 2; i <= n; ++i)
{
if (dp[i-1] + a[i] < a[i])
dp[i] = dp[i-1] + a[i];
else
{
st = i;
dp[i] = a[i];
}
if (minim > dp[i])
{
minim = dp[i];
ans_left = st;
ans_right = i;
}
}
int max_sum = total - minim;
int length = (ans_right >= ans_left) ? (ans_right - ans_left + 1) : (n - ans_left + ans_right + 1);
cout << max_sum << " " << ans_left + 1 << " " << length << "\n";
return 0;
}