Pagini recente » Cod sursa (job #1896475) | Cod sursa (job #1635745) | Cod sursa (job #1625444) | Cod sursa (job #1036836) | Cod sursa (job #1718187)
#include <fstream>
#include <deque>
#define INF 1000000
#define DIM 500000
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n , type , pos , mx = - INF, lg;
int v[DIM] , sum[DIM];
deque <int> coada;
int main() {
f >> n;
for (int i = 1; i <= n; ++i) {
f >> v[i] >> type;
if (!type) {
v[i] = -v[i];
}
}
for (int i = 1; i <= n; ++i) {
v[n + i] = v[i];
}
for (int i = 1; i <= 2 * n; ++i) {
sum[i] = sum[i - 1] + v[i];
}
coada.push_back(1);
for (int i = 2; i <= 2 * n; ++i) {
while (!coada.empty() && i - coada.front() >= n) {
coada.pop_front();
}
if (sum[i] - sum[coada.front()] > mx) {
mx = sum[i] - sum[coada.front()];
pos = coada.front() + 1;
lg = i - coada.front();
}
else
if (sum[i] - sum[coada.front()] == mx) {
int qq = coada.front() + 1;
if (pos > qq) {
pos = qq;
lg = i - coada.front();
}
else {
if (pos == qq)
lg = min(lg , i - coada.front());
}
}
while (!coada.empty() && sum[coada.back()] > sum[i]) {
coada.pop_back();
}
coada.push_back(i);
}
g << mx << " " << pos << " " << lg;
return 0;
}