Pagini recente » Cod sursa (job #777286) | Cod sursa (job #619597) | Borderou de evaluare (job #1007029) | Cod sursa (job #378557) | Cod sursa (job #3165521)
#include <iostream>
#include <fstream>
#define DIM 10006
std::ifstream fin("buline.in");
std::ofstream fout("buline.out");
using namespace std;
int N, a[DIM];
int total_sum;
void Read()
{
total_sum=0;
fin>>N;
for(int val, semn, i=1;i<=N;i++) {
fin>>val>>semn;
total_sum += (a[i]=(semn==1 ? 1 : -1)*val);
}
}
void Solve()
{
/// cazul 1: nu trece prin mijloc, i.e. nu foloseste faptul ca sirul este circular
int smax=a[1];
int sum=a[1], st1=1, be_st1=1, be_dr1=1;
for(int i=2;i<=N;i++) {
if(sum<0)
sum=0, st1=i;
sum+=a[i];
if(sum>smax)
smax=sum, be_st1=st1, be_dr1=i;
else if(sum==smax) {
if(st1 < be_st1 || (st1 == be_st1 && i < be_dr1))
be_st1=st1, be_dr1=i;
}
}
/// cazul 2: trece prin mijloc, i.e. este de forma
/**
[st2 ... n-1 n 1 2 ... dr2] = suma maxima
= [1 ... n] - [st2+1 ... dr2-1] = suma maxima
s fixa
deci [st2 ... dr2] = suma minima, secventa care nu trece prin mijloc , deci necircular
*/
int smin=a[1];
sum=a[1]; int st2=1, be_st2=1, be_dr2=1;
for(int i=2;i<=N;i++) {
if(sum>0)
sum=0, st2=i;
sum+=a[i];
if(sum<smin)
smin=sum, be_st2=st2, be_dr2=i;
else if(sum==smin) {
if(st2 < be_st2 || (st1 == be_st1 && i > be_dr2))
be_st2=st2, be_dr2=i;
}
}
int circmax = total_sum - smin;
/// comparam si dam raspuns
int P1=be_st1, L1 = be_dr1-be_st1+1;
int P2=be_st2+1, L2 = N - (be_dr2-be_st2+1);
int best, Pb, Lb;
if(smax > circmax) best=smax, Pb=P1, Lb=L1;
else if(circmax > smax) best=circmax, Pb=P2, Lb=L2;
else {
best=smax;
if(P1 < P2) Pb=P1, Lb=L1;
else if(P2 < P1) Pb=P2, Lb=L2;
else {
Pb=P1;
if(L1 < L2) Lb=L1;
else if(L2 < L1) Lb=L2;
else Lb=L1;
}
}
fout<<best<<" "<<Pb<<" "<<Lb;
}
int main()
{
Read();
Solve();
return 0;
}