Submission #1290682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290682		AlgorithmWarrior	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	21 ms	416 KiB

Main

#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;
}

• 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