Cod sursa(job #2488549)

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

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

int n, a[400005];

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)
    {
        dp[i].val=max(max(dp[i-1].val+a[i],a[i]),0);
        if (dp[i].val==a[i])
            dp[i].start=i;
        else
            dp[i].start=dp[i-1].start;
    }
    int ind=n+1;
    int dublu=2*n;
    while(1 && ind<=dublu)
    {
        dp[ind].val=max(max(dp[ind-1].val+a[ind],a[ind]),0);
        if (dp[ind].val==a[ind] && dp[ind].val==0)
            break;
        else
            dp[ind].start=dp[ind-1].start;
        if (ind-dp[ind].start==n)
            break;
        ++ind;
    }
    int maxi=-1, ind_start, l;
    for (int i=1; i<=2*n; ++i)
    {
        if (dp[i].val>maxi)
        {
            maxi=dp[i].val;
            ind_start=dp[i].start;
            l=i-dp[i].start+1;
        }
    }
    g << maxi <<' '<<ind_start <<' '<<l;
    return 0;
}