Cod sursa(job #2687308)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 19 decembrie 2020 18:47:11
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int sp[400005], v[200005];
pair <int, int> minsp[400005];
int main()
{
    int n, a, b, k;
    fin>>n;
    for (int i=1; i<=n; i++) {
        fin>>a>>b;
        if (b==0) a*=-1;
        k=a;
        v[i]=k;
        sp[i]=sp[i-1]+k;
        if (sp[i]<minsp[i-1].first) {
            minsp[i].first=sp[i];
            minsp[i].second=i;
        }
        else {
            minsp[i].first=minsp[i-1].first;
            minsp[i].second=minsp[i-1].second;
        }
    }
    for (int i=n+1; i<=n; i++) {
        k=v[i-n];
        sp[i]=sp[i-1]+k;
        if (sp[i]<minsp[i-1].first) {
            minsp[i].first=sp[i];
            minsp[i].second=i;
        }
        else {
            minsp[i].first=minsp[i-1].first;
            minsp[i].second=minsp[i-1].second;
        }
    }
    int st, dr, maxval=0;
    for (int i=1; i<=2*n; i++) {
        if (sp[i]-minsp[i].first>maxval) {
            maxval=sp[i]-minsp[i].first;
            st=minsp[i].second;
            dr=i;
        }
    }
    fout<<maxval+1<<" "<<st+1<<" "<<dr-st+2;
    return 0;
}