Cod sursa(job #2516398)

Utilizator bluestorm57Vasile T bluestorm57 Data 31 decembrie 2019 12:22:10
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5 + 10;
const int inf = 2e9;
long long v[NMAX],n,a[NMAX];

int main(){
    long long i,j,x,y,pi,maxs,p,l,aux;
    long long sum = 0;
    f >> n;
    for(i = 1 ; i <= n ; i++){
        f >> x >> y;
        if(!y)
            v[i] = -x;
        else
            v[i] = x;
        sum += v[i];
    }

    pi = 1;
    maxs = p = l = -inf;
    for(i = 1 ; i <= n ; i++){
        if(a[i - 1] + v[i] > v[i])
            a[i] = a[i - 1] + v[i];
        else{
            a[i] = v[i];
            pi = i;
        }
        if(maxs < a[i]){
            maxs = a[i];
            p = pi;
            l = i - pi + 1;
        }else
            if(maxs == a[i]){
                if(pi < p){
                    p = pi;
                    l = i - pi + 1;
                }else
                    if(p == pi && l > i - pi + 1)
                        l = i - pi + 1;
            }
    }


    pi = 1;
    for(i = 1 ; i <= n ; i++){
        if(a[i - 1] + v[i] < v[i])
            a[i] = a[i - 1] + v[i];
        else{
            a[i] = v[i];
            pi = i;
        }
        if(maxs < sum - a[i]){
            maxs = sum - a[i];
            p = (i + 1) % n;
            if(!p)
                p = n;
            l = n - (i - pi + 1);
        }
        else
            if(maxs == sum - a[i]){
                aux =( i + 1 % n);
                if(!aux)
                    aux = n;
                if(aux < p){
                    p = aux;
                    l = n - (i - pi + 1);
            }
            else
                if(p == aux && l > i - pi + 1)
                    l = n - (i - pi + 1);
        }
    }

    g << maxs << " " <<  p << " " << l;
    return 0;
}