Pagini recente » Cod sursa (job #731533) | Cod sursa (job #658382) | Cod sursa (job #948144) | simulare-cartita-10 | Cod sursa (job #2765394)
#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;
l = i - first + 1;
}
if (S < 0) {
first = i + 1;
S = 0;
}
}
st = first, L = l;
// 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;
}