Dakimakura Distribition Codechef Solution

by

Dakimakura Distribition Codechef Solution

Only a few centuries later, the Berland government realized what was necessary for the country’s prosperity. That’s right, a dakimakura for every resident of Berland!

It is known that Berland consists of NN cities, where CiCi people live in city ii and it takes TiTi hours to get from city ii to city i+1i+1.

See Also : July Long Challenge 2021 Solutions Codechef

The government is ready to allocate xx tugriks for the implementation of the project to give out dakimakuras. They also agreed with local producers, so the dakimakuras themselves are free.

To implement the project, the government can open a branch for issuing dakimakuras free of charge in several cities. For each city with an open branch for issuing dakimakuras, the government can pay 11 tugrik to increase its productivity by 11 unit. It can be increased any number of times, so that a productivity of kk units costs kk tugriks.

Then the issuance of dakimakuras begins. For each resident of the country that is located in city ii, he/she will travel to the first city with index greater or equal to ii that has a branch. Recall, it takes TiTi hours to travel from city ii to i+1i+1. After arrival, he/she enters the queue in the branch.

For each branch, it handles the queue as follows.

  • Let the productivity of this branch be pp. If there are less than pp people in the queue, then the branch issues dakimakuras to everyone in the queue. Otherwise, it starts with the first pp people, and gives them dakimakuras. A branch can only give dakimakuras every hour (that is, integer times since the start). Also, a resident cannot receive a dakimakura at the same moment he/she enters the queue.

You must find the minimum amount of time required for the government to issue dakimakuras to all residents of Berland, spending no more than xx tugriks in total. Assume all the residents start travelling at the same time, and the branches also opened at hour 00.

Input

  • The first line contains a single integer tt – the number of test cases. Then tt test cases follow.
  • The first line of each test case contains two integers NN and xx – the number of cities in Berland and the maximum amount of tugriks that the government can spend.
  • The second line contains NN integers C1,…,CnC1,…,Cn.
  • The third line contains N−1N−1 integers T1,…,Tn−1T1,…,Tn−1.

Output

For each test case, print in a single line the answer to the problem.

Constraints

  • 1≤t≤51≤t≤5
  • 2≤N≤1002≤N≤100
  • 1≤x≤1091≤x≤109
  • 0≤Ci≤1090≤Ci≤109
  • 1≤Ti≤1091≤Ti≤109

Subtasks

  • Subtask 1 (20 points): 2≤N≤82≤N≤8, 1≤x,Ti≤81≤x,Ti≤8 and 0≤Ci≤80≤Ci≤8
  • Subtask 2 (20 points): x=1x=1
  • Subtask 3 (40 points): 2≤N≤402≤N≤40
  • Subtask 4 (20 points): Original constraints

Sample Input

2
5 6
8 3 1 5 0
1 1 1 1
5 1
2 8 0 0 1
7 3 1 2

Sample Output

3
16

Explanation

The first test case:

Let’s open a branch in city 11 with productivity 33 and one in city 44 with productivity 33.

Then in the 00-th hour, 88 people in city 11 and 55 people in city 44 will enter the queues in their respective cities. Meanwhile, the people in cities 22 and 33 will travel to the next city.

Then in the 11-st hour, 33 people in city 11 and 33 people in city 44 will receive dakimakuras. Now the numbers of remaining people in each city are [5,0,3,3,0][5,0,3,3,0].

Then in the 22-nd hour, 33 people in city 11 and 33 people in city 44 will receive dakimakuras. Now the numbers of remaining people in each city are [2,0,0,3,0][2,0,0,3,0].

Then in the 33-rd hour, 22 people in city 11 and 33 people in city 44 will receive dakimakuras. Now, every resident in Berland has received a dakimakura, so the process took 33 hours.

Solution

#include <bits/stdc++.h> 
using namespace std;

#define int long long
#define mm(lamb, tttt) memset(lamb, tttt, sizeof lamb)
#define sz(a) (int)a.size()
#define mod 1000000007
#define debn(x) cout<<#x<<'='<<x<<endl
#define deb(x) cout<<#x<<'='<<x <<' '
#define deb2(x,y) cout<<#x <<'='<<x<<' ' <<#y<<'='<<y<<' '
#define deb2n(x,y) cout<<#x <<'='<<x<<' ' <<#y<<'='<<y<<endl 
#define deb3(x,y,z) cout<<#x <<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<' ' 
#define deb3n(x,y,z) cout<<#x <<'='<<x<<' '<<#y<<'='<<y<<' '<<#z<<'='<<z<<endl 
#define in(ar,n) for(int i=0;i<(int)n;i++)cin>>ar[i];
#define out(ar,n) cout<<#ar<<endl; for(int i=0;i<(int)n;i++) cout<<i+1<<'-'<<ar[i+1]<<","; cout<<endl;
#define ub upper_bound
#define lb lower_bound
#define prt(s)  cout<<"s" 
#define prtn(s)  cout<<"s"<<endl 
#define khtm cout<<endl 
#define pb push_back
#define pf push_front
#define F first
#define S second
#define asc(a) sort(a.begin(),a.end())
#define desc(a) sort(a.begin(),a.end(),greater <int> ())
#define all(a) a.begin(),a.end()

typedef vector <int> vi;

int32_t main()
{
    int testcases;
    cin >> testcases;
    while(testcases--)
    {
        int n,x,sum=0,last=0;
        cin >> n >> x;
        vi a(n),t(n),p(n);
        for(int i=0;i<n;i++)
        {
            cin >> a[i];
            sum+=a[i];
            if(a[i]>0)
            last=i;
        }
        p[0]=0;
        for(int i=0;i<n-1;i++)
        {
            cin >> t[i];
            p[i+1]=p[i]+t[i];
        }
        int ans=0;
        if(x==1)
        {
            for(int i=last;i>=0;i--)
            {
            ans=max(p[last]-p[i],ans);
            ans+=a[i];
           
            }
            cout<<ans<<endl;
            continue;
        }
        int mx=min(x,1000ll);
        ans=LONG_LONG_MAX;
        vi coat=a;
        for(int k=0;k<last;k++)
        {
            for(int j=1;j<mx;j++)
            {
                a=coat;
                int temp1=0,temp2=0;
               
                for(int i=k;i>=0;i--)
                {
                    if(a[i]<=0)
                    {
                       
                    continue;
                    }
                    temp1=max(temp1,p[k]-p[i]);
                  
                    temp1+=(a[i]/(mx-j));
                  
                    if(a[i]%(mx-j)!=0)
                    {
                        if(i-1>=0 and temp1>=p[k]-p[i-1])
                        {
                            a[i-1]-=(mx-j-a[i]%(mx-j));
                        }
                    temp1++;
                    }
                 
                }
                for(int i=last;i>k;i--)
                {
                    if(a[i]<=0)
                    {
                      
                    continue;}
                    temp2=max(temp2,p[last]-p[i]);
                    temp2+=(a[i]/(j));
                    if(a[i]%(j)!=0)
                    {
                        if(temp2>=p[last]-p[i-1])
                        {
                            a[i-1]-=(j-a[i]%j);
                        }
                    temp2++;
                    }
                }
                ans=min(ans,max(temp1,temp2));
                
            }
               
        }
        int temp2=0;
        for(int i=last;i>=0;i--)
        {
            if(a[i]<=0)
            {
            continue;}
            temp2=max(temp2,p[last]-p[i]);
            temp2+=(a[i]/(x));
            if(a[i]%(x)!=0 )
            {
                if(i!=last and i!=0 and temp2>=p[last]-p[i-1])
                {
                    a[i-1]-=(x-a[i]%x);
                }
                temp2++;
            }
          
        }
        ans=min(ans,temp2);
        cout<<ans<<endl;
    }
}

July Long Challenge 2021 Solutions

Weekly Contest 247

Biweekly Contest 55

Leave a Comment

three + 1 =