Pagini recente » Istoria paginii runda/123456789012 | Cod sursa (job #1096419) | Cod sursa (job #1355965) | Cod sursa (job #708167) | Cod sursa (job #1005346)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const int Nmax = 400005;
int N;
deque <int> DQ;
long long A[Nmax];
long long best, start, finish;
void read()
{
ifstream f("buline.in");
f >> N;
for ( int i = 1, tip; i <= N; ++i )
{
f >> A[i] >> tip;
if ( tip == 0 )
A[i] *= ( - 1 );
else
A[i] = A[i];
}
for ( int i = N + 1; i < 2 * N; ++i )
A[i] = A[i - N];
for ( int i = 1; i < 2 * N; ++i )
A[i] += A[i - 1];
f.close();
}
void solve()
{
for ( int i = 1; i < 2 * N; ++i )
{
while ( !DQ.empty() && DQ.front() <= i - N )
DQ.pop_front();
while ( !DQ.empty() && A[ DQ.back() ] > A[i] )
DQ.pop_back();
DQ.push_back( i );
if ( A[i] - A[ DQ.front() ] > best )
{
best = A[i] - A[ DQ.front() ];
start = DQ.front() + 1;
finish = i - DQ.front();
}
}
}
void print()
{
ofstream g("buline.out");
g << best << " " << start << " " << finish << "\n";
g.close();
}
int main()
{
read();
solve();
print();
return 0;
}