Submission #38834499

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define all(v) v.begin(),v.end() 
typedef long long ll;
typedef pair<int, int> pii;

int dm=0;

void solve()
{
    int n,m;
    cin>>n>>m;

    int b[n]; 
    long long ans[m];
    pair<int, int> c[m]; 
    for(int i=0; i<n; i++) cin>>b[i];
    
    for(int i=0; i<m; i++){
        cin>>c[i].first;
        c[i].second = i;
    }
    sort(b, b+n, greater<int>());
    sort(c, c+m);

    function<void(int, int, int, int)> solve = [&](int st, int end, int sst, int send){
        if(sst == send){
            for(int i=st; i<=end; i++){
                ans[c[i].second] = sst * (ll)(b[sst-1]+c[i].first);
            }
        }
        else if(st == end){
            auto [x, idx] = c[st];
            ans[idx] = 0;
            for(int t=sst; t<=send; t++){
                ans[idx] = max(ans[idx], t * (ll)(b[t-1] + x));
            }
        }
        else if(st<=end){
            int mid = (st+end)/2;
            auto [x, idx] = c[mid];
            int k = -1;
            ans[idx] = 0;
            for(int t=sst; t<=send; t++){
                long long curans = t * (ll)(b[t-1] + x);
                if(curans > ans[idx]){
                    k = t;
                    ans[idx] = curans;
                }
            }

            solve(st, mid-1, sst, k);
            solve(mid+1, end, k, send);

        }
    };

    solve(0, m-1, 1, n);

    for(int i=0; i<m; i++) cout << ans[i] << " ";


}

int main()
{
    #ifndef ONLINE_JUDGE
        dm = 1;
        freopen("input.txt", "r", stdin);
    #endif 
    if(!dm){ios::sync_with_stdio(false);cin.tie(0);}
    int t = 1;
    //cin >> t;
    while (t--)solve();
}

Submission Info

Judge Result