Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define vi vector<int>
- #define ll long long
- #define pb push_back
- #define fi first
- #define se second
- #define ii pair<int,int>
- #define ll long long
- const int MOD = 1e9 + 7;
- const int INF = 2e9 + 5;
- const int LEN = 5e4 + 5;
- // Link : CF - GYM NEERC 2012 - 2013 problem - K
- struct data {
- ll p,w;
- int id,len;
- };
- data ar[LEN];
- data seg[505];
- vi K;
- bool cmp(data a, data b) {
- return 1LL * b.w * a.p < 1LL * b.p * a.w;
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0);
- freopen ("student.in","r",stdin);
- freopen ("student.out","w",stdout);
- int n,sz = 0,x;
- cin>>n;
- for(int i =0;i<n;i++) {
- cin>>x;
- K.pb(x);
- sz += K[i];
- }
- for(int i =0;i<sz;i++) {
- cin>>ar[i].p;
- ar[i].id = i+1;
- }
- for(int i =0;i<sz;i++) {
- cin>>ar[i].w;
- }
- int pos = 0; ll p,w;
- for(int i =0;i<n;i++) {
- sort(ar+pos, ar + pos + K[i],cmp);
- p = 0;
- w = 0;
- for(int k =pos; k < pos + K[i];k++) {
- p += (1LL * ar[k].p);
- w += (1LL * ar[k].w);
- }
- pos += K[i];
- seg[i] = { p, w, ar[pos-1].id, K[i]};
- }
- sort(seg,seg+n,cmp);
- ll ans = 0;
- vi idx;
- int t = 0;
- for(int i =0;i<n;i++) {
- for(int k = seg[i].id-seg[i].len; k < seg[i].id; k++) {
- t += ar[k].p;
- ans += 1LL * t * ar[k].w;
- idx.pb(ar[k].id);
- }
- }
- cout<<ans<<"\n";
- for(int i =0;i<sz;i++) {
- cout<<idx[i]<<((i != sz-1) ? " " : "\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement