Submission #1311095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311095		wangzhiyi33	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	65 ms	4456 KiB

Main

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

int n,k;
vector<pair<int,int> >tmp;

double brp(int m){
    vector<vector<double> >dp(n+1,vector<double>(k+1,1e18));

    dp[0][0]=0;
    for(int q=1;q<=n;q++){
        for(int w=0;w<=min(k,q);w++){
            // ambil a nya
            if(w)dp[q][w]=min(dp[q][w],dp[q-1][w-1]+(double)(tmp[q].second)/(double)(m+1));

            // ambil b nya
            if((q-w)>m){
                dp[q][w]=min(dp[q][w],dp[q-1][w]);
            }
            else{
                dp[q][w]=min(dp[q][w],dp[q-1][w]+(double)(tmp[q].first)/(double)(q-w));
            }
            //cout<<q<<" "<<w<<" "<<dp[q][w]<<endl;
        }
    }
    return dp[n][k-m];
   
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    int a[n+1],b[n+1];
    tmp.push_back({0,0});

    int hah=0;
    for(int q=1;q<=n;q++){
        cin>>a[q]>>b[q];
        if(b[q]==-1)tmp.push_back({1e18,a[q]});
        else tmp.push_back({b[q],a[q]}),hah++;
    }
    sort(tmp.begin(),tmp.end());

    int l=0,r=min(k,hah);
    // for(int q=0;q<=k;q++){
    //     cout<<brp(q)<<endl;
    // }
    double ans=1e18;
    while(r-l>2){
        int mid1=l+(r-l)/3;
        int mid2=r-(r-l)/3;

        double satu=brp(mid1),dua=brp(mid2);
        if(satu<dua){
            ans=min(ans,satu);
            r=mid2-1;
        }
        else{
            ans=min(ans,dua);
            l=mid1+1;
        }
    }

    for(int q=l;q<=r;q++){
        ans=min(ans,brp(q));
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;
}

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