Cod sursa(job #1461821)

Utilizator Iulia_ivanaIulia Ivana Iulia_ivana Data 16 iulie 2015 15:32:47
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>
using namespace std;

ifstream in("buline.in");
ofstream out("buline.out");

int x[400001];

int main(){
    int n,sc,ic,im,sfm,smax;
    in>>n;
    for(int i=1; i<=n; i++){
        in>>x[i];
        int k;
        in>>k;
        if(k==0) x[i]*=-1;
    }

    sc=smax=x[1];
    ic=im=sfm=1;
    for(int i=2; i<=n; i++){
        if(sc+x[i]<x[i]){
            sc=x[i];
            ic=i;
        }
        else {
            sc+=x[i];
        }
        if(sc>smax){
            smax=sc;
            im=ic;
            sfm=i;
        }
    }

    int smax2,imin,sfmin,smin;
    sc=smin=x[1];
    ic=imin=sfmin=1;
    for(int i=2; i<=n; i++){
        if(sc+x[i]>x[i]){
            sc=x[i];
            ic=i;
        }
        else {
            sc+=x[i];
        }
        if(sc<smin){
            smin=sc;
            imin=ic;
            sfmin=i;
        }
    }

    int stot=0;
    for(int i=1; i<=n; i++)
        stot+=x[i];

    smax2=stot-smin;

    if(smax>smax2){
        out<<smax<<" "<<im<<" "<<sfm-im+1;
    }
    else {
        out<<smax2<<" "<<(sfmin+1)%n<<" "<<n-sfmin+imin-1;
    }
    in.close();
    out.close();
    return 0;
}