Codeforces/hcr3.cpp at main · swati510/Codeforces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pi;
struct comp {
bool operator()(const pi &a,const pi &b){
    if(a.first==b.first)return a.second<b.second;
    return a.first<b.first;
}};
struct func{bool operator()( const pi &a,const pi &b){
    return a.first>b.first;
}};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin>>n>>k;
    int a[n],b[n],c[n];
    set<pi,comp>start;
    set<pi,func>cmp;
    for(int i=0;i<n;i++){cin>>a[i];
    start.insert(make_pair(a[i],i));}
    for(int i=0;i<n;i++)cin>>b[i];
    for(int i=0;i<n;i++)cin>>c[i];

    int finall[n]={0};
     priority_queue <int, vector<int>, greater<int>> chef;
   int i=0; auto itr=start.begin();
    for( i=0;i<k;i++){

      //  finall[itr->second]=(itr->first);
        chef.push(0);
        // ++itr;

    }
    i=0; auto it=cmp.begin();
   while(itr!=start.end()){


      while((chef.top()>a[itr->second])){
          cmp.insert(make_pair((max(chef.top()-itr->second,0)+b[itr->second])*c[itr->second],itr->second));

          ++itr;
         if(itr==start.end())break;
      }

     if(cmp.begin()==cmp.end()){if(itr!=start.end()) {
        cmp.insert(make_pair((max(chef.top()-itr->second,0)+b[itr->second])*c[itr->second],itr->second));
          ++itr;

      }
      else break;
      }
      it=cmp.begin();

      finall[it->second]=max(chef.top(),a[it->second]);
     chef.pop();
      chef.push(finall[it->second]+b[it->second]);
      cmp.erase(it);
      ++it;
    }

    while(it!=cmp.end()){
        it=cmp.begin();
         finall[it->second]=max(chef.top(),a[it->second]);
         chef.pop();
      chef.push(finall[it->second]+b[it->second]);
            cmp.erase(it);
      ++it;


    }
    for(int i=0;i<n;i++)cout<<finall[i]<<" ";


    return 0;
}