Cod sursa(job #3165656)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 6 noiembrie 2023 18:16:17
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <climits>

using namespace std;

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

const int DIM = 200010;

int n;
int v[DIM], sum;

struct seq {
    int sum, ind, len;
} maxx, minn, best1, best2, worst;

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        int num, color;
        fin >> num >> color;
        v[i] = (color ? num : -num);
        sum += v[i];
    }

    best1.sum = INT_MIN, worst.sum = INT_MAX;
    for (int i = 1; i <= n; i++) {
        if (maxx.sum + v[i] >= v[i]) {
            maxx.sum += v[i];
            maxx.len++;
        } else {
            maxx.sum = v[i];
            maxx.ind = i;
            maxx.len = 1;
        }
        if (maxx.sum > best1.sum)
            best1 = maxx;

        if (minn.sum + v[i] <= v[i]) {
            minn.sum += v[i];
            minn.len++;
        } else {
            minn.sum = v[i];
            minn.ind = i;
            minn.len = 1;
        }
        if (minn.sum < worst.sum)
            worst = minn;
    }
    best2.sum = sum - worst.sum;
    best2.ind = worst.ind + worst.len;
    best2.len = n - worst.len;

    seq best = (best1.sum >= best2.sum ? best1 : best2);
    fout << best.sum << ' ' << best.ind << ' ' << best.len;

    return 0;
}