Cod sursa(job #934708)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 31 martie 2013 02:46:59
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <deque>
#include <iterator>
#include <limits>
#include <cstring>

#define MAXN 400003

using namespace std;

long long vec[MAXN];
long long sums[MAXN];

int main()
{
    int n;
    fstream fin("buline.in", fstream::in);
    fstream fout("buline.out", fstream::out);
    
    fin >> n;
    //cout << n << endl;
    
    for (int i=1; i<=n; ++i)
    {
        int sgn;
        fin >> vec[i] >> sgn;
        
        vec[i] *= (sgn ? 1 : -1);
    }
    
    memcpy(vec + n + 1, vec+1, n * sizeof(long long));
    
    /*ostream_iterator<short> itOutS(cout, " ");
    copy(vec, vec + 2*n + 1, itOutS);
    cout << endl << endl;*/

    partial_sum(vec, vec + 2*n + 1, sums);
    
    /*ostream_iterator<long long> itOutLL(cout, " ");
    copy(sums, sums + 2*n + 1, itOutLL);
    cout << endl;*/
    
    int pos = -1;
    int length = 0;
    long long maxSum = numeric_limits<long long>::min();
    deque<int> deq;
    
    for (int i=1; i<2*n; ++i)
    {
        while (!deq.empty() && sums[deq.back()] >= sums[i-1])
        {
            deq.pop_back();
        }
        deq.push_back(i-1);
        
        if (deq.front() < i - n)
        {
            deq.pop_front();
        }
        
        if (sums[i] - sums[deq.front()] > maxSum)
        {
            maxSum = sums[i] - sums[deq.front()];
            pos = deq.front() + 1;
            length = i - deq.front();
        }
        else if (sums[i] - sums[deq.front()] == maxSum)
        {
            if (pos == deq.front() + 1)
            {
                length = min(length, i - deq.front());
            }
            else if (pos > deq.front() + 1)
            {
                pos = deq.front() + 1;
                length = i - deq.front();
            }
        }
    }
    
    fout << maxSum << " " << pos << " " << length << "\n";
    
    return 0;
}