_Nocturnal

C-Working

Apr 29th, 2021
51
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define M 1000000007
  5. #define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define PI 3.14159265
  7. #define pb push_back
  8. #define LLMX LONG_LONG_MAX
  9. #define LLMN LONG_LONG_MIN
  10. #define double long double
  11. vector < int > arr ;
  12. set < int > st ;
  13. vector < int > graph[3003] ;
  14. int n , m , k;
  15. map < pair < pair < int , int > , int > , int > dp ;
  16. bool comp( vector < int > &a , vector < int > &b)
  17. {
  18. if( (signed)a.size() > (signed)b.size())
  19. return true ;
  20. else
  21. return false ;
  22. }
  23. vector < int > university[200005] ;
  24. signed main()
  25. {
  26. fastio ;
  27. int T ;
  28. cin >> T ;
  29. while( T--)
  30. {
  31. st.clear() ;
  32. cin >> n ;
  33. vector < int > u , s;
  34. for(int x = 1 ; x <= n ; x++)
  35. {
  36. int t;
  37. cin >> t ;
  38. u.pb(t) ;
  39. st.insert(t) ;
  40. }
  41. for(int x = 1 ; x <= n ; x++)
  42. {
  43. int t;
  44. cin >> t ;
  45. s.pb(t) ;
  46. }
  47. for(auto it = st.begin() ; it != st.end() ; it++)
  48. university[*it].clear() ;
  49.  
  50. for(int x = 0 ; x < n ; x++)
  51. university[u[x]].pb(s[x]) ;
  52.  
  53. for(auto it = st.begin() ; it != st.end() ; it++)
  54. sort(university[*it].begin() , university[*it].end() , greater < int >()) ;
  55.  
  56. vector < vector < int > > temp ;
  57. for(auto it = st.begin() ; it != st.end() ; it++)
  58. {
  59. int sum = 0 ;
  60. for(int x = 0 ; x < university[*it].size() ; x++)
  61. {
  62. sum = sum + university[*it][x] ;
  63. university[*it][x] = sum ;
  64. }
  65. }
  66. int maxi = LLMN ;
  67. for(auto it = st.begin() ; it != st.end() ; it++)
  68. {
  69. if( university[*it].size() > maxi)
  70. maxi = university[*it].size() ;
  71. temp.pb(university[*it]) ;
  72. }
  73. sort( temp.begin() , temp.end() , comp) ;
  74. for(int k = 1 ; k <= n ; k++)
  75. {
  76. if( k > maxi)
  77. {
  78. cout << "0 " ;
  79. continue ;
  80. }
  81. int sum = 0 ;
  82. for(auto it = temp.begin() ; it != temp.end() ; it++)
  83. {
  84. if( (*it).size() < k)
  85. break ;
  86.  
  87. for(int x = k -1 ; x < (signed)(*it).size() ; x = x + k )
  88. {
  89. if( x + k >= (*it).size())
  90. {
  91. sum = sum + (*it)[x] ;
  92. }
  93. }
  94. }
  95. cout << sum << " " ;
  96. }
  97. cout << "\n" ;
  98. }
  99. }
RAW Paste Data