Pagini recente » Cod sursa (job #2194954) | Cod sursa (job #1393098) | Cod sursa (job #1196936) | Cod sursa (job #3313658) | Cod sursa (job #3342144)
#include <fstream>
using namespace std;
long long s[400005];
int q[400005];
int val[200005], col[200005];
int main() {
ifstream fin("buline.in");
ofstream fout("buline.out");
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> val[i] >> col[i];
int x = (col[i] == 1) ? val[i] : -val[i];
s[i] = x;
s[i + n] = x;
}
for (int i = 1; i <= 2 * n; ++i) {
s[i] += s[i - 1];
}
long long s_max = -2000000001;
int p = 0, l = 0;
int head = 1, tail = 0;
q[++tail] = 0;
for (int i = 1; i <= 2 * n; ++i) {
while (head <= tail && q[head] < i - n) {
head++;
}
if (head <= tail) {
long long s_curr = s[i] - s[q[head]];
int l_curr = i - q[head];
int p_curr = q[head] + 1;
if (p_curr > n) p_curr -= n;
if (s_curr > s_max) {
s_max = s_curr;
p = p_curr;
l = l_curr;
} else if (s_curr == s_max) {
if (p_curr < p) {
p = p_curr;
l = l_curr;
} else if (p_curr == p && l_curr < l) {
l = l_curr;
}
}
}
while (head <= tail && s[q[tail]] >= s[i]) {
tail--;
}
q[++tail] = i;
}
fout << s_max << " " << p << " " << l << "\n";
return 0;
}