Mai intai trebuie sa te autentifici.
Cod sursa(job #833336)
Utilizator | Data | 12 decembrie 2012 14:30:59 | |
---|---|---|---|
Problema | Buline | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.04 kb |
#include <fstream>
using namespace std;
int const N=200000;
short b[N];
int n;
int S, P, L;
int dp1[N];
int dp2[N];
//dp1[i]=suma maxima pana la i
//dp2[i]=suma minima pana la i
int sgn(int a){
return a<0;
}
int ST;
int Sm, SM;
int Pm, PM;
int Lm, LM;
int Lmc, LMc;
int main(){
ifstream f("buline.in");
f>>n;
int i;
int x;
for(i=0; i<n; i++){
f>>b[i];
f>>x;
b[i]=x?b[i]:-b[i];
dp1[i]=b[i];
dp2[i]=b[i];
ST+=b[i];
}
f.close();
SM=Sm=b[0];
PM=Pm=0;
LM=Lm=LMc=Lmc=1;
for(i=1; i<n; i++){
if(dp1[i-1]>0){
dp1[i]+=dp1[i-1];
LMc++;
}else{
LMc=1;
}
if(dp1[i]>SM){
SM=dp1[i];
PM=i-LMc+1;
LM=LMc;
}
if(dp2[i-1]<0){
dp2[i]+=dp2[i-1];
Lmc++;
}else{
Lmc=1;
}
if(dp2[i]<Sm){
Sm=dp2[i];
Pm=i-Lmc+1;
Lm=Lmc;
}
}
if(SM>ST-Sm){
S=SM;
P=PM;
L=LM;
}else{
S=ST-Sm;
P=Pm+Lm;
L=n-Lm;
}
ofstream g("buline.out");
g<<S<<" "<<P+1<<" "<<L;
g.close();
return 0;
}