Cod sursa(job #3146121)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 18 august 2023 16:56:17
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <climits>

using namespace std;

const int DIM = 200010;

int n;
int v[DIM];

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

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

    int bestSum = INT_MIN, bestStart = 0, bestLen = 0;
    int sum = 0, start = 1, len = 0;
    for (int i = 1; i <= n; i++) {
        if (sum < 0) {
            sum = v[i];
            start = i;
            len = 1;
        } else {
            sum += v[i];
            len++;
        }

        if (sum > bestSum && len <= n) {
            bestSum = sum;
            bestStart = start;
            bestLen = len;
        }
    }
    for (int i = 1; i < start; i++) {
        if (sum < 0) {
            sum = v[i];
            start = i;
            len = 1;
        } else {
            sum += v[i];
            len++;
        }

        if (sum > bestSum && len <= n) {
            bestSum = sum;
            bestStart = start;
            bestLen = len;
        }
    }

    fout << bestSum << ' ' << bestStart << ' ' << bestLen;

    fin.close();
    fout.close();
    return 0;
}