Cod sursa(job #2121163)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 3 februarie 2018 13:23:40
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n, v[200002], s[200002], bests[200002]={INT_MIN}, pozbs[200002];
int sum=INT_MIN, smax=INT_MIN, sv, lsv;
int main()
{
    int i, tip, st;
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>v[i]>>tip;
        if(tip==0) v[i]*=(-1);
        s[i]=s[i-1]+v[i];
        if(bests[i-1]<s[i])
        {
            bests[i]=s[i];
            pozbs[i]=i;
        }
        else
        {
            bests[i]=bests[i-1];
            pozbs[i]=pozbs[i-1];
        }
    }
    for(i=1; i<=n; i++)
    {
        if(sum<0) sum=v[i], st=i;
        else sum+=v[i];
        if(sum>smax) smax=sum, sv=st, lsv=i-st+1;
    }
    for(i=2; i<=n; i++)
    {
        sum=bests[i-1]+s[n]-s[i-1];
        if(sum>smax) smax=sum, sv=i, lsv=n-i+1+pozbs[i];
    }
    fout<<smax<<' '<<sv<<' '<<lsv<<'\n';
    return 0;
}