Pagini recente » Cod sursa (job #3148528) | Cod sursa (job #215703) | Cod sursa (job #1221288) | Cod sursa (job #1264088) | Cod sursa (job #3192104)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
struct answer {
long long value = LLONG_MIN;
int pivot = 0;
int length = 0;
} ans;
int main() {
int n;
fin >> n;
vector<int> v(n+1);
for (int i = 1; i <= n; i++) {
int type;
fin >> v[i];
fin >> type;
if (!type) {
v[i]*=-1;
}
}
int pivot = 1;
int length = 1;
int s = v[1];
if (s > ans.value) {
ans = {s,pivot,length};
} else if(s == ans.value) {
if(pivot < ans.pivot) {
ans = {s,pivot,length};
} else if (pivot == ans.pivot
&& length < ans.length) {
ans = {s,pivot,length};
}
}
for (int i = 2; i <= n; i++) {
if (v[i] + s >= v[i]) {
length++;
s+=v[i];
} else {
length = 1;
pivot = i;
s = v[i];
}
if (s > ans.value) {
ans = {s,pivot,length};
} else if(s == ans.value) {
if(pivot < ans.pivot) {
ans = {s,pivot,length};
} else if (pivot == ans.pivot
&& length < ans.length) {
ans = {s,pivot,length};
}
}
}
const int _pivot = pivot;
pivot = 1;
length = 1;
answer ans2;
ans2.value = LLONG_MAX;
s = v[1];
if (s < ans2.value) {
ans2 = {s,pivot,length};
} else if(s == ans2.value) {
if(pivot > ans2.pivot) {
ans2 = {s,pivot,length};
} else if (pivot == ans2.pivot
&& length > ans2.length) {
ans2 = {s,pivot,length};
}
}
for (int i = 2; i <= n; i++) {
if (v[i] + s <= v[i]) {
length++;
s+=v[i];
} else {
length = 1;
pivot = i;
s = v[i];
}
if (s < ans2.value) {
ans2 = {s,pivot,length};
} else if(s == ans2.value) {
if(pivot > ans2.pivot) {
ans2 = {s,pivot,length};
} else if (pivot == ans2.pivot
&& length > ans2.length) {
ans2 = {s,pivot,length};
}
}
}
int sum = 0;
for (int i = 1; i < ans2.pivot; i++) {
sum += v[i];
}
for (int i = ans2.pivot + ans2.length; i <= n; i++) {
sum += v[i];
}
if (ans.value < sum) {
ans.value = sum;
ans.pivot = ans2.pivot + ans2.length;
ans.length = n - ans2.length;
}
fout << ans.value << ' ' << ans.pivot << ' ' << ans.length;
return 0;
}