Submission #1009325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009325		Aiperiii	Self Study (JOI22_ho_t2)	C++14	10 / 100	42 ms	5072 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    bool s=1;
    vector <int> a(n),b(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        cin>>b[i];
        if(a[i]!=b[i])s=0;
    }
    if(m==1){
        int res=1e9;
        for(int i=0;i<n;i++){
            res=min(res,max(a[i],b[i]));
        }
        cout<<res<<"\n";
    }
    else if(s){
        int l=0,r=1e18;
        int ans=0;
        while(l<=r){
            int md=(l+r)/2;
            int sum=0,mn=1e18;
            for(int i=0;i<n;i++){
                int x=md/a[i];
                if(md%a[i]!=0)x++;
                sum+=x;
                mn=min(mn,a[i]*x);
            }
            if(sum<=n*m){
                ans=max(ans,mn);
                l=md+1;
            }
            else r=md-1;
        }
        cout<<ans<<"\n";
    }
    else{
        set <pair <int,int> > st;
        vector <int> cnt(n);
        for(int i=0;i<n;i++){
            st.insert({max(a[i],b[i]),i});
            if(a[i]>b[i])cnt[i]++;
        }
        for(int i=0;i<m*n-n;i++){
            int x=st.begin()->ff;
            int id=st.begin()->ss;
            st.erase(st.begin());
            if(a[id]>b[id] && cnt[id]<m){
                x+=a[id];
                cnt[id]++;
            }
            else x+=b[id];
            st.insert({x,id});
            
        }
        cout<<st.begin()->ff<<"\n";
        /*for(auto x : st){
            cout<<x.ff<<" "<<x.ss<<'\n';
        }*/
    }
}
/*
 4 25
 1 2 3 4
 1 2 3 4
 12 6 3 4
 3 3
 19 4 5
 2 6 2
 
 5 60000
 630510219 369411957 874325200 990002527 567203997
 438920902 634940661 593780254 315929832 420627496
*/

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 9