Pagini recente » Cod sursa (job #528522) | Cod sursa (job #424529) | Cod sursa (job #2802316) | Cod sursa (job #3273652) | Cod sursa (job #882983)
Cod sursa(job #882983)
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
const int Nmax = 400009;
int N; int V[Nmax]; long long S[Nmax]; deque<int> Q;
void Read(){
fin >>N;
for(int i = 1; i <= N; ++i){
int A, B; fin >>A >>B;
if(B == 0) B = -1;
V[i] = A * B;
}
for(int i = 1; i <= N; ++i)
V[i + N] = V[i];
for(int i = 1; i <= N + N; ++i)
S[i] = S[i - 1] + V[i];
}
void Solve(){
int Smax = (-1) * (1<<30);int PosMax = 0; int LenghtMax = 0; Q.push_back(0);
for(int i = 1; i <= N + N ;++i){
int Now = S[i] - S[Q.front()];
int Pos = Q.front() + 1;
int Lenght = i - Pos + 1;
if(Smax < Now ||(Smax == Now && Pos < PosMax ) ||(Smax == Now && Pos == PosMax && LenghtMax > Lenght))
Smax = Now, PosMax = Pos, LenghtMax = Lenght;
while(!Q.empty() && S[i] <= S[Q.back()])
Q.pop_back();
Q.push_back(i);
if(i >= N + Q.front())
Q.pop_front();
}
PosMax %= N + 1;
fout << Smax <<" "<<PosMax <<" "<<LenghtMax;
}
int main(){
Read(); Solve ();
return 0;
}