Cod sursa(job #2547133)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 15 februarie 2020 00:32:52
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,cod,sum,sol,st,lung,cnt,i,v[DIM],s[DIM],d[DIM],ind[DIM];
int main() {
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i]>>cod;
        if (!cod)
            v[i]=-v[i];
    }
    for (i=1;i<=n;i++) { //cand sirul nu e circular
        if (sum<=0)
            sum=0, cnt=i;
        sum+=v[i];
        if (sum>sol) {
            sol=sum;
            st=cnt;
            lung=i-cnt+1;
        }
    }
    for (i=1;i<=n;i++) {
        s[i]=s[i-1]+v[i];
        if (d[i-1]>s[i]) {
            d[i]=d[i-1];
            ind[i]=ind[i-1];
        }
        else {
            d[i]=s[i];
            ind[i]=i;
        }
    }
    for (i=1;i<=n;i++) {
        if (sol<d[i-1]+s[n]-s[i-1]) {
            sol=d[i-1]+s[n]-s[i-1];
            st=i;
            lung=n+ind[i-1]-i+1;
        }
    }
    fout<<sol<<" "<<st<<" "<<lung;
    return 0;
}