Submission #1224805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224805		TadijaSebez	Let's Win the Election (JOI22_ho_t3)	C++20	27 / 100	97 ms	4424 KiB

Main

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

const int N=505;
const int M=5005;

const ldb inf=1e18;
const int bm1=1e9;

ldb dp[N][M];
int a[N],b[N],ord[N],mn[N];
int main(){
    int n,k;
    scanf("%i %i",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%i %i",&a[i],&b[i]);
        ord[i]=i;
        if(b[i]==-1)b[i]=bm1;
    }
    sort(ord+1,ord+1+n,[&](int i,int j){return make_pair(b[i],a[i])<make_pair(b[j],a[j]);});
    set<int> tmp;
    for(int i=n;i>k;i--){
        tmp.insert(a[ord[i]]);
    }
    for(int i=k;i>=1;i--){
        mn[i]=mn[i+1];
        tmp.insert(a[ord[i]]);
        mn[i]+=*tmp.begin();
        tmp.erase(tmp.begin());
    }
    ldb ans=mn[1];
    for(int take=0;take<=k;take++){
        for(int i=0;i<=k;i++){
            for(int j=0;j<=k;j++){
                dp[i][j]=inf;
            }
        }
        dp[0][0]=0;

        for(int i=1;i<=k;i++){
            for(int j=0;j<=min(i,take);j++){
                dp[i][j]=dp[i-1][j]+(ldb)a[ord[i]]/(take+1);
                if(j>0 && b[ord[i]]!=bm1){
                    dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(ldb)b[ord[i]]/j);
                }
            }
            if(i>=take){
                ans=min(ans,dp[i][take]+(ldb)mn[i+1]/(take+1));
            }
        }
    }
    printf("%.12lf\n",ans);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%i %i",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%i %i",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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