Cod sursa(job #1747515)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 25 august 2016 00:42:12
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("buline.in");
ofstream out("buline.out");
const int maxn = 400005;
int v[maxn];
int main()
{
    int n;
    in >> n;
    for(int i = 1; i <= n; i++)
    {
        int aux;
        in >> v[i] >> aux;
        if(aux == 0)
            v[i] = -v[i];
        v[i + n] = v[i];
    }
    int maxsum = -(1 << 30);
    int s = -1;
    int st = 0;
    int rezst = 1;
    int rezdr = 1;
    for(int i = 1; i <= n * 2; i++)
    {
        if(s < 0)
        {
            s = 0;
            st = i;
        }
        if(i - st == n)
        {
            s -= v[st];
            st++;
        }
        s += v[i];
        if(maxsum < s)
        {
            maxsum = s;
            rezst = st;
            rezdr = i;
        }
    }
    out << maxsum << " " << rezst << " " << rezdr - rezst + 1 << "\n";
    return 0;
}