Cod sursa(job #2167587)

Utilizator tqmiSzasz Tamas tqmi Data 13 martie 2018 22:23:52
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
#define Nmax 2*200005
#define oo 2000000000
using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

int N,m=-oo,mi,ml,x,y;
int dp[Nmax],L[Nmax],A[200005];

int main()
{
    fin>>N;
    dp[0] = -oo;
    for(int i=1;i<=N;i++){
        fin>>x>>y;
        dp[i] = dp[i+N] = x;
        if(y==0){
            dp[i] *=(-1);
            dp[i+N] *= (-1);
        }
        A[i] = dp[i];
        L[i] = L[i+N] = 1;
    }
    for(int i=1;i<=2*N;++i){
        if(L[i-1]<N){
            if(dp[i]+dp[i-1]>dp[i]){
                dp[i] +=dp[i-1];
                L[i] = L[i-1]+1;
            }
        }
        else{
            if(dp[i]+dp[i-1]-A[i-N]>dp[i]){
                dp[i] = dp[i]+dp[i-1]-A[i-N];
                L[i] = N;
            }
        }
        if(dp[i]>m){
            m=dp[i];
            mi=i;
            ml = L[i];
        }
    }
    if(mi-ml+1>N)
        mi-=N;
    fout<<m<<" "<<mi-ml+1<<" "<<ml<<"\n";
    return 0;
}