Submission #824361

#	Time	Username	Problem	Language	Result	Execution time	Memory
824361		ttamx	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	1 ms	340 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N=505;

typedef long double ld;

int n,m;
ld a[N],b[N];
ld ans=LDBL_MAX;
int orda[N],ordb[N];
bool used[N];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> a[i] >> b[i];
    for(int i=1;i<=n;i++)if(b[i]==-1)b[i]=1005;
    iota(orda,orda+n+1,0);
    iota(ordb,ordb+n+1,0);
    sort(orda+1,orda+n+1,[&](int x,int y){
        return a[x]<a[y];
    });
    sort(ordb+1,ordb+n+1,[&](int x,int y){
        if(b[x]==b[y])return a[x]>a[y];
        return b[x]<b[y];
    });
    ld cost=0;
    for(int i=1;i<=n;i++){
        ld res=cost;
        int cnt=i-1;
        for(int j=1;cnt<m;j++){
            if(used[orda[j]])continue;
            res+=a[orda[j]]/i;
            cnt++;
        }
        ans=min(ans,res);
        if(b[ordb[i]]>1000)break;
        cost+=b[ordb[i]]/i;
        used[ordb[i]]=true;
    }
    cout << fixed << setprecision(12) << ans;
}

• 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