Pagini recente » Cod sursa (job #958223) | Cod sursa (job #1193075) | Cod sursa (job #1163760) | Cod sursa (job #1356237) | Cod sursa (job #767753)
Cod sursa(job #767753)
#include <fstream>
#include <queue>
using namespace std;
int N, S = -20000, poz, poz2;
int v[400005];
deque <pair <int, int> > dq;
void Citire () {
int a;
ifstream fin ("buline.in");
fin >> N;
for (int i = 0; i < N; i++)
{
fin >> v[i] >> a;
v[i] = (a ? v[i] : -v[i]);
v[i + N] = v[i];
if (S < v[i])
{
S = v[i];
poz = i;
poz2 = i;
}
}
for (int i = 1; i < N << 1; i++)
v[i] += v[i - 1];
fin.close ();
}
void Business () {
for (int i = 0; i < N + N; i++)
{
if (!dq.empty () && i - dq.front ().second > N) dq.pop_front ();
while (!dq.empty () && dq.back ().first > v[i]) dq.pop_back ();
dq.push_back (make_pair (v[i], i));
if (v[i] - dq.front ().first > S)
{
S = v[i] - dq.front ().first;
poz = dq.front ().second;
poz2 = i;
}
}
}
void Scriere () {
ofstream fout ("buline.out");
fout << S << " " << poz + 2 << " " << poz2 - poz;
fout.close ();
}
int main () {
Citire ();
Business ();
Scriere ();
return 0;
}