Submission #1167502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167502		Newtonabc	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	1 ms	328 KiB

Main

#include<bits/stdc++.h>
using namespace std;
double a[1000],b[1000];
bool mark[1000];
vector<int> v,sorta;
//keep index
bool compare(int tmpa,int tmpb){
    if(b[tmpa]<b[tmpb]) return true;
    if(b[tmpb]<b[tmpa]) return false;
    if(a[tmpa]>a[tmpb]) return true;
    return false;
}
bool cp(int tmpa,int tmpb){
    if(a[tmpa]<a[tmpb]) return true;
    return false;
}
int main(){
    int n,k;
    cin>>n >>k;
    for(int i=1;i<=n;i++){
        cin>>a[i] >>b[i];
        sorta.push_back(i);
        if(b[i]!=-1) v.push_back(i);
    }
    sort(v.begin(),v.end(),compare);
    sort(sorta.begin(),sorta.end(),cp);
    int mx=v.size();
    mx=min(mx,k);
    double ans=INT_MAX;
    for(int use=0;use<=mx;use++){
        for(int i=1;i<=n;i++) mark[i]=false;
        double cand=0,pow=1;
        for(int i=0;i<use;i++){
            int ind=v[i];
            mark[ind]=true;
            cand+=b[ind]/pow;
            pow++;
        }
        int left=k-use,cnt=0,nowind=0;
        while(cnt<left){
            int ind=sorta[nowind];
            if(mark[ind]){
                nowind++;
                continue;
            }
            cand+=a[ind]/pow;
            nowind++;
            cnt++;
        }
        ans=min(ans,cand);
    }
    cout<<fixed <<setprecision(7) <<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