Cod sursa(job #2811367)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 1 decembrie 2021 23:48:31
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

int a[400001];
int N, o, poz, pp, len;

int pozzz(int i) {
    if(i <= N)
        return i;
    return i - N;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("buline");

    cin >> N;
    for(int i = 1;i <= N;i++) {
        cin >> a[i] >> o;
        if(o == 0) a[i] = -a[i];
    }

    for(int i = N + 1;i <= 2 * N;i++)
        a[i] = a[i - N];

    long long sum = 0, mx = LLONG_MIN;

    for(int i = 1;i <= 2 * N;i++) {
        sum += a[i];

        if(sum > mx && i - poz + 1 <= N) {
            mx = sum, pp = pozzz(poz), len = i - poz + 1;
        } else if(sum == mx && i - poz + 1 <= N) {
            if(pozzz(i) < pp) pp = pozzz(i), len = i - poz + 1;
            else if(pozzz(i) == pp && i - poz + 1 < len) len = i - poz + 1;
        }

        if(sum < 0) 
            sum = 0, poz = i + 1;
    }

    cout << mx << " " << pp << " " << len;

    return 0;
}