Cod sursa(job #2488572)

Utilizator altcontnoualt cont altcontnou Data 7 noiembrie 2019 09:20:09
Problema Buline Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

ifstream f("buline.in");
ofstream g("buline.out");

int n, a[400005], s;

deque<int>deck;

struct p
{
    int val, start;
} dp[400005];

int x, tip;

int main()
{
    f >> n;
    for (int i=1; i<=n; ++i)
    {
        f >> x >> tip;
        if (tip==0)
        {
            a[i]=a[n+i]=-x;
        }
        else
        {
            a[i]=a[n+i]=x;
        }
    }
    for (int i=1; i<=n; ++i)
    {
        s+=a[i];
        if (s<=0)
        {
            while (!deck.empty())
            {
                s-=a[deck.front()];
                deck.pop_front();
            }
            s=0;
        }
        else
        {
            deck.push_back(i);
            dp[i].start=deck.front();
        }
        dp[i].val=s;

    }
    int dublu=2*n;
    for (int i=n+1; i<=dublu; ++i)
    {
        s+=a[i];
        if (s<=0)
        {
            while (!deck.empty())
                {
                    s-=a[deck.front()];
                    deck.pop_front();
                }
            s=0;
        }
        else
        {
            deck.push_back(i);
            while (deck.back()-deck.front()+1>n)
                {
                    s-=a[deck.front()];
                    deck.pop_front();
                }
            dp[i].start=deck.front();
        }
        dp[i].val=s;
    }
    int maxi=-1, l, poz;
    for (int i=1; i<=dublu; ++i)
    {
        if (dp[i].val>maxi)
        {
            maxi=dp[i].val;
            poz=dp[i].start;
            l=i-dp[i].start+1;
        }
        else if (dp[i].val==maxi)
        {
            if (dp[i].start<l)
            {
                poz=dp[i].start;
                l=i-dp[i].start+1;
            }
            else if (i-dp[i].start+1<l)
            {
                poz=dp[i].start;
                l=i-dp[i].start+1;
            }
        }
    }
    g << maxi <<' '<<poz <<' '<<l;
    return 0;
}