Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2019
706
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define vi vector<int>
  4. #define ll long long
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8. #define ii pair<int,int>
  9. #define ll long long
  10. const int MOD = 1e9 + 7;
  11. const int INF = 2e9 + 5;
  12. const int LEN = 5e4 + 5;
  13. // Link : CF - GYM NEERC 2012 - 2013 problem - K
  14. struct data {
  15. ll p,w;
  16. int id,len;
  17. };
  18. data ar[LEN];
  19. data seg[505];
  20. vi K;
  21. bool cmp(data a, data b) {
  22. return 1LL * b.w * a.p < 1LL * b.p * a.w;
  23. }
  24.  
  25. int main() {
  26. ios_base::sync_with_stdio(0); cin.tie(0);
  27. freopen ("student.in","r",stdin);
  28. freopen ("student.out","w",stdout);
  29. int n,sz = 0,x;
  30. cin>>n;
  31. for(int i =0;i<n;i++) {
  32. cin>>x;
  33. K.pb(x);
  34. sz += K[i];
  35. }
  36.  
  37. for(int i =0;i<sz;i++) {
  38. cin>>ar[i].p;
  39. ar[i].id = i+1;
  40. }
  41. for(int i =0;i<sz;i++) {
  42. cin>>ar[i].w;
  43. }
  44. int pos = 0; ll p,w;
  45. for(int i =0;i<n;i++) {
  46. sort(ar+pos, ar + pos + K[i],cmp);
  47. p = 0;
  48. w = 0;
  49. for(int k =pos; k < pos + K[i];k++) {
  50. p += (1LL * ar[k].p);
  51. w += (1LL * ar[k].w);
  52. }
  53. pos += K[i];
  54. seg[i] = { p, w, ar[pos-1].id, K[i]};
  55. }
  56.  
  57. sort(seg,seg+n,cmp);
  58.  
  59. ll ans = 0;
  60. vi idx;
  61. int t = 0;
  62. for(int i =0;i<n;i++) {
  63. for(int k = seg[i].id-seg[i].len; k < seg[i].id; k++) {
  64. t += ar[k].p;
  65. ans += 1LL * t * ar[k].w;
  66. idx.pb(ar[k].id);
  67. }
  68. }
  69. cout<<ans<<"\n";
  70. for(int i =0;i<sz;i++) {
  71. cout<<idx[i]<<((i != sz-1) ? " " : "\n");
  72. }
  73.  
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement