Pagini recente » Cod sursa (job #2769958) | Cod sursa (job #1379131) | Cod sursa (job #2350127) | Borderou de evaluare (job #2051233) | Cod sursa (job #3236965)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
#include <cmath>
#define ll long long
#define ld long double
std::ifstream cin("buline.in");
std::ofstream cout("buline.out");
const int NMAX = 2e5;
const int INF = 2e9;
struct Triplet {
int max_sum, left, length;
bool operator < (const Triplet &other) const {
if(max_sum > other.max_sum) {
return true;
}
if(max_sum == other.max_sum && left < other.left) {
return true;
}
if(max_sum == other.max_sum && left == other.left && length < other.length) {
return true;
}
return false;
}
};
int n, sum, max_sum, start, left, length;
int a[NMAX + 1];
Triplet dp_prefix[NMAX + 5], dp_suffix[NMAX + 5];
Triplet answer;
int main() {
std::ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
a[i] = (y == 1 ? x : -x);
}
max_sum = -INF;
sum = 0;
start = 1;
left = 0;
length = 0;
answer = {max_sum, left, length};
for(int i = 1; i <= n; i++) {
sum += a[i];
if(sum > max_sum) {
max_sum = sum;
left = start;
length = i - left + 1;
}
if(sum < 0) {
sum = 0;
start = i + 1;
}
answer = std::min(answer, {max_sum, left, length});
}
sum = 0;
for(int i = 1; i <= n; i++) {
sum += a[i];
dp_prefix[i] = std::min(dp_prefix[i - 1], {sum, 1, i});
}
sum = 0;
for(int i = n; i >= 1; i--) {
sum += a[i];
dp_suffix[i] = std::min(dp_suffix[i + 1], {sum, i, n - i + 1});
}
for(int i = 1; i <= n - 1; i++) {
answer = std::min(answer, {dp_prefix[i].max_sum + dp_suffix[i + 1].max_sum, dp_suffix[i + 1].left, dp_prefix[i].length + dp_suffix[i + 1].length});
}
cout << answer.max_sum << ' ' << answer.left << ' ' << answer.length << '\n';
return 0;
}