Cod sursa(job #2170710)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 15 martie 2018 09:30:18
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>

using namespace std;
const int nmax=1e5+3;
long long n,t[nmax],v[nmax],mn,st,dr,mij,sol,ad[nmax],mars[nmax],act;
int main()
{
      cin>>n;
      for(int i=1;i<=n;++i) cin>>v[i];
      for(int i=1;i<=n;++i)
      {
            cin>>t[i];
            t[i]+=t[i-1];
      }
      for(int i=1;i<=n;++i)
      {
            mn=t[i-1];
            st=i-1;
            dr=n;
            while(st<=dr)
            {
                  mij=(st+dr)/2;
                  if(t[mij]-mn<=v[i])
                  {
                        sol=mij;
                        st=mij+1;
                        continue;
                  }
                  else
                  {
                        dr=mij-1;
                        continue;
                  }
            }
            ad[sol+1]+=v[i]-t[sol]+mn;
            ++mars[i];
            --mars[sol+1];
      }
      for(int i=1;i<=n;++i) mars[i]+=mars[i-1];
      for(int i=1;i<=n;++i)
      {
            act=mars[i]*(t[i]-t[i-1])+ad[i];
            cout<<act<<' ';
      }
      return 0;
}