Cod sursa(job #3192101)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 11 ianuarie 2024 15:46:06
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
struct answer {
    long long value = LLONG_MIN;
    int pivot = 0;
    int length = 0;
} ans;


int main() {
    int n;
    fin >> n;
    vector<int> v(n+1);
    for (int i = 1; i <= n; i++) {
        int type;
        fin >> v[i];
        fin >> type;
        if (!type) {
            v[i]*=-1;
        }
    }
    int pivot = 1;
    int length = 1;
    int s = v[1];
    if (s > ans.value) {
        ans = {s,pivot,length};
    } else if(s == ans.value) {
        if(pivot < ans.pivot) {
            ans = {s,pivot,length};
        } else if (pivot == ans.pivot
                   && length < ans.length) {
            ans = {s,pivot,length};
        }
    }
    for (int i = 2; i <= n; i++) {
        if (v[i] + s >= v[i]) {
            length++;
            s+=v[i];
        } else {
            length = 1;
            pivot = i;
            s = v[i];
        }
        if (s > ans.value) {
            ans = {s,pivot,length};
        } else if(s == ans.value) {
            if(pivot < ans.pivot) {
                ans = {s,pivot,length};
            } else if (pivot == ans.pivot
                       && length < ans.length) {
                ans = {s,pivot,length};
            }
        }
    }

    const int _pivot = pivot;
    pivot = 1;
    length = 1;
    answer ans2;
    ans2.value = LLONG_MAX;
    s = v[1];
    if (s < ans2.value) {
        ans2 = {s,pivot,length};
    } else if(s == ans2.value) {
        if(pivot > ans2.pivot) {
            ans2 = {s,pivot,length};
        } else if (pivot == ans2.pivot
                   && length > ans2.length) {
            ans2 = {s,pivot,length};
        }
    }
    for (int i = 2; i <= n; i++) {
        if (v[i] + s <= v[i]) {
            length++;
            s+=v[i];
        } else {
            length = 1;
            pivot = i;
            s = v[i];
        }
        if (s < ans2.value) {
            ans2 = {s,pivot,length};
        } else if(s == ans2.value) {
            if(pivot > ans2.pivot) {
                ans2 = {s,pivot,length};
            } else if (pivot == ans2.pivot
                       && length > ans2.length) {
                ans2 = {s,pivot,length};
            }
        }
    }
    int sum = 0;
    for (int i = 1; i < ans2.pivot; i++) {
        sum += v[i];
    }
    for (int i = ans2.pivot + ans2.length; i <= n; i++) {
        sum += v[i];
    }
    if (ans.value < sum) {
        ans.value = sum;
        ans.pivot = ans.pivot + ans2.length - 1;
        ans.length = n - ans2.length;
    }
    fout << ans.value << ' ' << ans.pivot << ' ' << ans.length;
    return 0;
}