제출 #1311076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311076		wangzhiyi33	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	1 ms	348 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#pragma GCC optimize("O3,unroll-loops")
#define fir first
#define sec second
#define pb push_back

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    int a[n+1],b[n+1];
    vector<pair<int,int> >bgs;
    priority_queue<int>pakai;
    priority_queue<int,vector<int>,greater<int> > tmp;

    for(int q=1;q<=n;q++){
        cin>>a[q]>>b[q];
        if(b[q]!=-1)bgs.pb({b[q],a[q]});
        else tmp.push(a[q]);
    }
    sort(bgs.begin(),bgs.end());

    int ans[n+2]; memset(ans,0,sizeof ans);
    int sum=0;

    if(k>=bgs.size()){
        for(int q=1;q<=max(0LL,k-(int)bgs.size());q++){
            int apa=tmp.top(); tmp.pop();
            pakai.push(apa); sum+=apa;
        }
        ans[bgs.size()]=sum;
    }

    for(int q=(int)bgs.size()-1;q>=k;q--){
        pair<int,int>cur=bgs[q];
        tmp.push(cur.sec);
    }

    for(int q=min(k-1,(int)bgs.size()-1);q>=0;q--){
        pair<int,int>cur=bgs[q];
        tmp.push(cur.sec);
        ans[q]=ans[q+1];

        while(pakai.size()<k-q){
            int apa=tmp.top(); tmp.pop();
            pakai.push(apa);
            ans[q]+=apa;
        }

        while(tmp.size() && pakai.size() && tmp.top()<pakai.top()){
            int bu=tmp.top(),ms=pakai.top();
            tmp.pop(),pakai.pop();
            tmp.push(ms),pakai.push(bu);
            ans[q]+=(bu-ms);
        }   
        //cout<<ans[q]<<"K"<<q<<endl;
    }

    double tot=0;
    double mn=ans[0];

    for(int q=1;q<=min(k,(int)bgs.size());q++){
        tot+=(double)(bgs[q-1].first)/(double)(q);
        double brp=(double)(ans[q])/(double)(q+1);
        mn=min(mn,tot+brp);
    }
    cout<<fixed<<setprecision(10)<<mn<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23