Submission #1009264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009264		Aiperiii	Self Study (JOI22_ho_t2)	C++14	62 / 100	1031 ms	15956 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;
    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(m==1){
        int res=1e9;
        for(int i=0;i<n;i++){
            res=min(res,max(a[i],b[i]));
        }
        cout<<res<<"\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";
    }
}
/*
 4 25
 1 2 3 4
 1 2 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: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 9