Cod sursa(job #2120738)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 2 februarie 2018 20:31:07
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#define DIM 200002
#define INF 2e9

using namespace std;

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

int n, x, y, stmax, stmax2, lgmax, lgmax2, maxim, maxim2, v[DIM], sumall, st;

int main()
{
    in>>n;
    for(int i = 1; i <= n; ++ i){
        in>>x>>y;
        if(y == 1)
            v[i] = x;
        else
            v[i] = -x;
        sumall += v[i];
    }

    int s = -INF;
    for(int i = 1; i <= n; ++ i){
        if(s < 0){
            s = v[i];
            st = i;
        }
        else
            s += v[i];
        if(s == maxim && st == stmax && i - st + 1 < lgmax){
            lgmax = i - st + 1;
        }
        if(s > maxim){
            maxim = s;
            stmax = st;
            lgmax = i - st + 1;
        }
    }

    s = v[1];
    st = 1;
    maxim2 = v[1];
    stmax2 = 1;
    lgmax2 = 1;
    for(int i = 2; i <= n; ++ i){
        if(s > 0){
            s = v[i];
            st = i;
        }
        else
            s += v[i];
        if(s == maxim2 && i - st + 1 > lgmax2){
            stmax2 = st;
            lgmax2 = i - st + 1;
        }
        if(s < maxim2){
            maxim2 = s;
            stmax2 = st;
            lgmax2 = i - st + 1;
        }
    }

    if(sumall - maxim2 > maxim)
        out<<sumall - maxim2<<" "<<stmax2 + lgmax2<<" "<<n - lgmax2;
    else
        out<<maxim<<" "<<stmax<<" "<<lgmax;

    return 0;
}