Cod sursa(job #2516396)

Utilizator bluestorm57Vasile T bluestorm57 Data 31 decembrie 2019 12:15:05
Problema Buline Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 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;
int v[NMAX],n,a[NMAX];

int main(){
    int 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];
            p = 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;
}