Pagini recente » Solutii FMI No Stress 4 | Diferente pentru teorema-chineza-a-resturilor intre reviziile 76 si 75 | Cod sursa (job #232176) | Cod sursa (job #216946) | Cod sursa (job #3165655)
#include <fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int DIM = 200010;
int n;
int v[DIM], sum;
struct seq {
int sum, ind, len;
} maxx, minn, best1, best2, worst;
int main() {
fin >> n;
for (int i = 1; i <= n; i++) {
int num, color;
fin >> num >> color;
v[i] = (color ? num : -num);
sum += v[i];
}
best1.sum = INT_MIN, worst.sum = INT_MAX;
for (int i = 1; i <= n; i++) {
if (maxx.sum + v[i] >= v[i]) {
maxx.sum += v[i];
maxx.len++;
} else {
maxx.sum = v[i];
maxx.ind = i;
maxx.len = 1;
}
if (maxx.sum > best1.sum)
best1 = maxx;
if (minn.sum + v[i] <= v[i]) {
minn.sum += v[i];
minn.len++;
} else {
minn.sum = v[i];
minn.ind = i;
minn.len = 1;
}
if (minn.sum < worst.sum)
worst = minn;
}
best2.sum = sum - worst.sum;
best2.ind = worst.ind + worst.len;
best2.len = n - worst.len;
seq best = (best1.sum >= best2.sum ? best1 : best2);
fout << best.sum << ' ' << best.ind << ' ' << best.len;
return 0;
}