Cod sursa(job #2130652)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 13 februarie 2018 20:00:49
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#define INF 2000000000
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,p,a[400005],x,mx,x1,q,mn,p1,last,pi;
bool b;
void Operation(int poz)
  {int i;
   mn=1;x1=0;p1=last;
   for(i=last+1;i<=poz;i++)
      {x1+=a[i];
       if(x1<mn){mn=x1;p1=i;}
      }
  }
int main()
{int i;
 fin>>n;
 for(i=1;i<=n;i++)
    {fin>>x>>b;
     if(b==1)a[i]=x;
     else a[i]=-x;
    }
 for(i=n+1;i<=2*n;i++)
    a[i]=a[i-n];
 mx=a[1];
 x=0;
 last=1;
 for(i=1;i<=2*n;i++)
    {if(i-last>=n){Operation(i);x-=a[last];if(mn<1){last=p1+1;x+=-mn;//fout<<"(("<<last<<"))";
                                                   }
                  }
        if(x+a[i]<=0){x=0;last=i+1;}
     else {x=x+a[i];
           if(x>mx){mx=x;p=i;pi=last;}
          }
          //fout<<i<<" "<<last<<"\n";
    }
 fout<<mx<<" "<<pi<<" "<<p-pi+1;
}