Submission #1237662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237662		warrenn	Let's Win the Election (JOI22_ho_t3)	C++20	11 / 100	467 ms	6308 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define double long double

bool cmp(pair<int,int>a,pair<int,int>b){
    if(a.second==-1 && b.second==-1){
        return a.first<b.first;
    }
    else if(a.second==-1)return false;
    else if(b.second==-1)return true;
    if(a.second!=b.second)return a.second<b.second;
    return a.first<b.first;
}

signed main(){
    int n,k;
    cin>>n>>k;
    pair<int,int>isi[n+1];
    for(int q=1;q<=n;q++){
        cin>>isi[q].first>>isi[q].second;
    }
    sort(isi+1,isi+n+1,cmp);
    int suff[n+2][k+1];
    for(int q=1;q<=k;q++){
        suff[n+1][q]=1e18;
    }
    suff[n+1][0]=0;

    for(int q=n;q>=1;q--){
        for(int w=0;w<=k;w++){
            suff[q][w]=1e18;
            // ambil
            if(w!=0){
                suff[q][w]=min(suff[q][w],suff[q+1][w-1]+isi[q].first);
            }
            // ga
            suff[q][w]=min(suff[q][w],suff[q+1][w]);
            
            //cout<<suff[q][w]<<" ";
            
        }
        //cout<<endl;
    }

    double ans=1e18;

    double dp[k+1][k+1];
    
    for(int buff=0;buff<=k;buff++){
        dp[0][0]=0;
        for(int q=1;q<=k;q++){
            dp[0][q]=1e18;
        }
        for(int q=1;q<=k;q++){
            for(int w=0;w<=buff;w++){
                dp[q][w]=1e18;
                if(q<w)continue;
                // ambil buff
                if(w!=0 && isi[q].second!=-1){
                    double waktu=(double)isi[q].second/(double)(w);
                    dp[q][w]=min(dp[q][w],dp[q-1][w-1]+waktu);
                }
                // ga ambil
                if(w!=buff){
                    double waktu=(double)isi[q].first/(double)(buff+1);
                    dp[q][w]=min(dp[q][w],dp[q-1][w]+waktu);
                }

                if(w==buff){
                    double sisa=suff[q+1][k-q]/(double)(buff+1);
                    // if(buff==0){
                    //     cout<<sisa<<" "<<q<<endl;
                    // }
                    ans=min(ans,dp[q][w]+sisa);
                }
            }   
        }
        

    }
    cout<<fixed<<setprecision(10)<<ans<<endl;
}

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