Pagini recente » Cod sursa (job #1688919) | Cod sursa (job #1205544) | Cod sursa (job #2196101) | Cod sursa (job #1919908) | Cod sursa (job #2166164)
#include<fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int NMax = 200005;
const int oo = 1 << 30;
int N,S1,P1,L1,Sum,S2,P2,L2;
int Best,Start;
int A[2 * NMax];
void Read()
{
fin>>N;
for(int i = 1 ; i <= N ; ++i)
{
int val; bool col;
fin >> val >> col;
if(!col) val *= -1;
A[i] = A[N + i] = val;
Sum += A[i];
}
}
void Solve()
{
Best = 0; Start = 1;
for(int i = 1 ; i <= 2 * N ; ++i)
{
if(A[i] + Best < A[i])
{
if(i > N) break;
Best = A[i];
Start = i;
}
else Best += A[i];
if(S1 < Best && i - Start + 1 <= N)
{
S1 = Best;
P1 = Start;
L1 = i - Start + 1;
}
}
Best = 0; Start = 1;
for(int i = 1 ; i <= 2 * N ; ++i)
{
if(A[i] + Best > A[i])
{
if(i > N) break;
Best = A[i];
Start = i;
}
else Best += A[i];
if(S2 > Best && i - Start + 1 <= N)
{
S2 = Best;
P2 = Start;
L2 = i - Start + 1;
}
}
P2 += L2 = 1;
L2 = N - L2;
if(Sum - S2 > S2 && L2 != 0)
{
S1 = Sum - S2;
P1 = P2;
L1 = L2;
}
}
void Print()
{
fout << S1 << " " << P1 << " " << L1 << "\n";
}
int main()
{
Read();
Solve();
Print();
fin.close();
fout.close();
return 0;
}