Cod sursa(job #2469501)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 7 octombrie 2019 16:41:22
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int v[400005];
long long best[400005];
int n,a,b,pozi,pozj,smax,pozimax,pozjmax,lg;
int main()
{
    fin >> n;
    for (int i=1;i<=n;i++)
    {
        fin >> a >> b;
        if (b == 0) {v[i] = -a;v[i+n] = -a;}
        else v[i] = a,v[i+n] = a;
    }
    smax = v[1];
    pozi = 1;
    pozj = 1;
    if (v[1] > 0) best[1] = v[1];
    else best[1] = 0;
    for (int i=2;i<2*n;i++)
    {
        best[i] = v[i];
        if (best[i] < best[i-1] + v[i] && i != pozi+n)
        {
            best[i] = best[i-1] + v[i];
            pozj++;
        }
        else
        {
            pozi = i;
            pozj = i;
        }
        if (smax < best[i])
        {
            smax = best[i];
            pozimax = pozi;
            pozjmax = pozj;
        }
    }
    lg = abs(pozjmax - pozimax + 1);
    if (pozimax > n) pozimax -= n;
    if (pozjmax > n) pozjmax -=n;
    fout << smax << " " << pozimax << " " << lg << '\n';
    return 0;
}