Pagini recente » Cod sursa (job #2020742) | Istoria paginii runda/oji_09_2012/clasament | Cod sursa (job #1350692) | Atasamentele paginii Clasament oji_in_iulie_lol | Cod sursa (job #2765398)
#include <fstream>
using namespace std;
int n;
int v[200001];
void read() {
int x, y, i;
ifstream f("buline.in");
f >> n;
for (i = 1; i <= n; i++) {
f >> x >> y;
if (y == 1)
v[i] = x;
else v[i] = -x;
}
f.close();
}
int st, L;
int Max = -2e9 - 1;
int sp[200001];
void solve() {
int i, S, first, l;
// momentam nu tratam circularitatea
first = 1;
S = 0;
for (i = 1; i <= n; i++) {
S += v[i];
if (S > Max) {
Max = S;
st = first;
L = (i - first + 1);
}
if (S < 0) {
first = i + 1;
S = 0;
}
}
// tratam circularitatea
for (i = 1; i <= n; i++)
sp[i] = sp[i - 1] + v[i];
int last, cMax = -2e9 - 1;
for (i = 1; i <= n - 1; i++) {
if (sp[i] > cMax) {
cMax = sp[i];
first = i;
}
if (cMax + sp[n] - sp[i] > Max) {
Max = cMax + sp[n] - sp[i];
st = i + 1;
L = first + (n - i);
}
}
}
void output() {
ofstream g("buline.out");
g << Max << ' ' << st << ' ' << L;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}