I'm happy to attend it and slove $$$5$$$ problems!

Hoping to do 5 problems

It's my first time to join this contest seriously.Good luck to me

I just solved 4 problems and gave up. It is too hard for me.

man , i dont know why my c dont is correct , aaaaa

after contest someone explain solution for D.

After contest, anyone explain approach for D and F, getting stuck in TLE :(

I loved problem E,gave D an hour and still can't do it,i'm really bad at geometry.

Looking at the number of ACs on Problem D, it was really disappointing that I couldn’t come up with the solution. Can anyone explain the solution to Problem D?

E was a bit painful

My thought process on $$$F$$$.

1. Bla
2. Bla
3. Bla
4. Implement a segment tree with operations $$$X$$$.

"Maybe I can avoid it? Let's try another idea."

1. Blo
2. Blo
3. Blo
4. Implement a segment tree with operations $$$Y$$$.

"Try again."

1. Blu
2. Blu
3. Blu
4. Implement a segment tree with operations $$$Z$$$.

Has anyone solved problem E using Lagrange multipliers?

Solving F by performing binary search on segment tree. Narrowly pass with 800+ms. When calculating the complexity during contest, always worrying about TLE

how e

With Problem E

I change the value of inf in following code from 1e18+1 to 2e18+1 will result in different answer. Why this happend

#include <bits/stdc++.h>
using namespace std;
typedef __uint128_t ll;
// typedef long long ll;
unsigned long long n, m;
vector<unsigned long long> a;
const long double inf = 1e18+1;
ll calcnt(ll p, ll limit)
{
    return (limit / p + 1) / 2;
}
ll calcost(ll limit)
{
    ll ans = 0;
    for (auto x : a)
    {
        ll cnt = calcnt(x, limit);
        if (x * cnt * cnt > inf)
            return inf;
        ans += cnt * cnt * x;
        if (ans > inf)
            return inf;
    }
    return ans;
}
unsigned long long cal(ll limit)
{
    ll ans = 0;
    for (auto x : a)
    {
        ll cnt = calcnt(x, limit);
        ans += cnt;
    }
    return ans;
}
int main()
{
    cin >> n >> m;
    a.resize(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    ll l = 0, r = 1e18;
    while (l < r)
    {
        ll mid = (l + r) / 2;
        if (calcost(mid) > m)
            r = mid;
        else
            l = mid + 1;
    }
    unsigned long long ans = cal(l - 1);
    m -= (unsigned long long)calcost(l - 1);
    cout << ans + m / (unsigned long long)l << endl;
}

Can someone explain the logic for E ? How is binary search applicable ?

E > F ?

But I still solve E :)

Problem E can be ACed using the Cauchy–Schwarz inequality with real numbers, followed by removing sub-optimal buys using a heap.

https://atcoder.jp/contests/abc389/submissions/61842706

Hi, I solved 5th question, this is my code, can someone point out what is my mistake?

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define all(x) (x).begin(),(x).end()
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];
    int s=0,e=1^18;
    int ans=-1;
    int pnt=0;
    int ss=0;
    while(s<=e){
        int mid=(e-s)/2+s;
        int sum=0;
        int cnt=0;
        for(int i=0; i<n; i++){
            int k=floor(sqrt(double(mid)/double(a[i])));
            sum+=(k*k*a[i]);
            cnt+=k;
        }
        if(sum<=m){
            ans=mid;
            ss=sum;
            pnt=cnt;
            s=mid+1;
        }
        else{
            e=mid-1;
        }
    }
    // cout<<pnt<<endl;
    // cout<<ans<<endl;
    //  cout<<m<<' '<<ss<<' '<<endl;
    pnt+=(m-ss)/(ans+1);
    cout<<pnt<<endl;

}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Can someone please find mistake.

Give clarity on this please.

In problem E. It calculated a price x(using binary search) for which we can by all items with price <=x. Such that total cost is <=M but there will be some remaining money. why is this remaining money used to buy as many items as possible of price x+1. (remaining_money)/(x+1). How we know if item priced x+1 will exist with surety and we can buy as many as possible.