fork download
  1. #include <iostream>
  2. #include <set>
  3. #include <queue>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. vector<long long int> xs;
  9. vector<long long int> ys;
  10. struct E{
  11. int x,y;
  12. long long int n;
  13. bool operator<(const E& e1)const{
  14. return n<e1.n;
  15. }
  16. };
  17. struct E2{
  18. int x,y;
  19. bool operator<(const E2& e2)const{
  20. if(x!=e2.x)return x<e2.x;
  21. return y<e2.y;
  22. }
  23. };
  24. priority_queue<E> pq;
  25. set<E2> ss;
  26.  
  27. int main() {
  28. int n,m,k;
  29. cin>>n>>m>>k;
  30. for(int i=0;i<n;i++){
  31. int x;
  32. cin>>x;
  33. xs.push_back(x);
  34. }
  35. for(int i=0;i<m;i++){
  36. int y;
  37. cin>>y;
  38. ys.push_back(y);
  39. }
  40. sort(xs.begin(), xs.end(), [](long long int a,long long int b) {
  41. return a > b;
  42. });
  43. sort(ys.begin(),ys.end(),[](long long int a,long long int b){
  44. return a>b;
  45. });
  46. E e1;
  47. e1.x=0;
  48. e1.y=0;
  49. e1.n=xs[0]+ys[0];
  50. pq.push(e1);
  51. while(0<k){
  52. E e1=pq.top();
  53. //cout<<e1.x<<" "<<e1.y<<" "<<xs[e1.x]<<" "<<ys[e1.y]<<endl;
  54. pq.pop();
  55. if(e1.x+e1.y!=0){
  56. cout<<" "<<e1.n;
  57. }else{
  58. cout<<e1.n;
  59. }
  60.  
  61. E2 e2;
  62. e2.x=e1.x+1;
  63. e2.y=e1.y;
  64. if(e2.x<n && ss.find(e2)==ss.end()){
  65. ss.insert(e2);
  66. E e1a;
  67. e1a.x=e2.x;
  68. e1a.y=e2.y;
  69. e1a.n=xs[e1a.x]+ys[e1.y];
  70. pq.push(e1a);
  71. }
  72. e2.x=e1.x;
  73. e2.y=e1.y+1;
  74. if(e2.y<m && ss.find(e2)==ss.end()){
  75. ss.insert(e2);
  76. E e1a;
  77. e1a.x=e2.x;
  78. e1a.y=e2.y;
  79. e1a.n=xs[e1a.x]+ys[e1a.y];
  80. pq.push(e1a);
  81. }
  82. k--;
  83. }
  84. cout<<endl;
  85. return 0;
  86. }
Success #stdin #stdout 0.01s 5304KB
stdin
9 6 24
201658578 622453475 401618362 972259033 185228408 328296266 992114820 83122445 361513303
378155906 294049442 328128273 980993661 260940296 989156892
stdout
1981271712 1973108481 1961415925 1953252694 1611610367 1603447136 1390775254 1382612023 1370270726 1350670195 1350414939 1342506964 1320243093 1317453158 1309289927 1300387306 1286164262 1266308475 1253055116 1233199329 1190815470 1182652239 1174385300 1166222069