Cod sursa(job #3342144)

Utilizator vlad.perpegel2010Vlad Perpegel vlad.perpegel2010 Data 23 februarie 2026 10:29:01
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>

using namespace std;

long long s[400005];
int q[400005];
int val[200005], col[200005];

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

    int n;
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> val[i] >> col[i];
        int x = (col[i] == 1) ? val[i] : -val[i];
        s[i] = x;
        s[i + n] = x;
    }
    for (int i = 1; i <= 2 * n; ++i) {
        s[i] += s[i - 1];
    }

    long long s_max = -2000000001;
    int p = 0, l = 0;

    int head = 1, tail = 0;
    q[++tail] = 0;

    for (int i = 1; i <= 2 * n; ++i) {
        while (head <= tail && q[head] < i - n) {
            head++;
        }

        if (head <= tail) {
            long long s_curr = s[i] - s[q[head]];
            int l_curr = i - q[head];
            int p_curr = q[head] + 1;

            if (p_curr > n) p_curr -= n;

            if (s_curr > s_max) {
                s_max = s_curr;
                p = p_curr;
                l = l_curr;
            } else if (s_curr == s_max) {
                if (p_curr < p) {
                    p = p_curr;
                    l = l_curr;
                } else if (p_curr == p && l_curr < l) {
                    l = l_curr;
                }
            }
        }

        while (head <= tail && s[q[tail]] >= s[i]) {
            tail--;
        }
        q[++tail] = i;
    }

    fout << s_max << " " << p << " " << l << "\n";

    return 0;
}