SHARE
TWEET

Untitled

a guest Nov 23rd, 2019 89 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 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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top