제출 #1290682

#제출 시각아이디문제언어결과실행 시간메모리
1290682AlgorithmWarriorLet's Win the Election (JOI22_ho_t3)C++20
10 / 100
21 ms416 KiB
#include <bits/stdc++.h>

using namespace std;

int const NMAX=505;
int n,k;
struct country{
    int a,b;
    bool votat;
}v[NMAX];

void read(){
    cin>>n>>k;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i].a>>v[i].b;
}

bool crt_a(country c1,country c2){
    return c1.a<c2.a;
}

bool crt_b(country c1,country c2){
    return c1.b<c2.b;
}

long double solve(int cnt){
    sort(v+1,v+n+1,crt_b);
    int i;
    for(i=1;v[i].b==-1;++i);
    if(n-i+1<cnt)
        return -1;
    int j;
    long double tot=0;
    int vorbitori=1;
    for(j=0;j<cnt;++j){
        tot+=1.0*v[i+j].b/vorbitori;
        ++vorbitori;
        v[i+j].votat=1;
    }
    sort(v+1,v+n+1,crt_a);
    int target=k-cnt;
    for(i=1;target;++i)
        if(!v[i].votat){
            v[i].votat=1;
            tot+=1.0*v[i].a/vorbitori;
            --target;
        }
    for(i=1;i<=n;++i)
        v[i].votat=0;
    return tot;
}

long double get_sol(){
    long double rsp=500000;
    int i;
    for(i=0;i<k;++i){
        long double temp=solve(i);
        if(temp!=-1 && rsp>temp)
            rsp=temp;
    }
    return rsp;
}

int main()
{
    read();
    cout<<fixed<<setprecision(5)<<get_sol();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...