Cod sursa(job #1050693)

Utilizator sebax538sebastian ghetu sebax538 Data 8 decembrie 2013 23:12:51
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
 
using namespace std;
 
ifstream f("buline.in");
ofstream g("buline.out");
int v[200001],s[200001],p,i,n,d,dd,pp,p2,p1,mi,mini,maxi,pl,ma,pi,pll;

int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>v[i]>>p;
        v[i + n] = v[i];
        if (p==0)
         v[i]= v[i+n] = -v[i];
        
    }
 
   int maxEndingHere = v[1];
        int maxSoFar = v[1];
        int begin_temp = 0, end = 0, begin = 0;
        int prev_end = 0, prev_begin = 0;
        int sum = v[1], currentSum = v[1], prevSum = v[1];

        for (int i = 1; i <= 2 * n; i++) {
            if (end - begin + 1 > n) {
                begin = prev_begin;
                end = prev_end;
                sum = prevSum;
                break;
            }
            // calculate max_ending_here
            if (maxEndingHere < 0) {
                maxEndingHere = v[i];
                currentSum = v[i];
                begin_temp = i;

            } else {
                maxEndingHere += v[i];
                currentSum += v[i];
            }

            // calculate max_so_far
            if (maxEndingHere >= maxSoFar) {
                maxSoFar = maxEndingHere;
                prevSum = sum;
                sum = currentSum;

                prev_begin = begin;
                begin = begin_temp;

                prev_end = end;
                end = i;
            }
        }

        if (end - begin + 1 > n) {
            end = prev_end;
            begin = prev_begin;
            sum = prevSum;
        }
      g<<sum<<" "<<begin<<" "<<end - begin + 1;
   f.close();
   g.close();
}