Cod sursa(job #2746801)

Utilizator As932Stanciu Andreea As932 Data 28 aprilie 2021 15:26:15
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>

using namespace std;

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

const int nmax = 2e5 + 5;

int n, v[2 * nmax];

void read(){
    fin >> n;

    for(int i = 1; i <= n; i++){
        int nr, sg;

        fin >> nr >> sg;

        if(!sg)
            nr *= (-1);

        v[i] = nr;
    }

    for(int i = 1; i <= n; i++)
        v[n + i] = v[i];
}

void solve(){
    long long s = 0, best = v[1];
    int f = 1, l = 1, r = 1;

    for(int i = 1; i <= 2 * n; i++){
        if(s < 0){
            s = 0;
            f = i;
        }

        s += v[i];

        if(i - n == f)
            s -= v[f++];

        if(s > best){
            best = s;
            l = f;
            r = i;
        }
    }

    fout << best << " " << l << " " << r - l + 1;
}

int main()
{
    read();
    solve();

    return 0;
}