Submission #891790

#	Time	Username	Problem	Language	Result	Execution time	Memory
891790		12345678	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	6 ms	392 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nx=505;
double n, k, a[nx], b[nx], cnt, c[nx];
double tmp, ans=DBL_MAX;
vector<pair<pair<double, double>, int>> v;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>a[i]>>b[i], cnt+=(b[i]!=-1), v.push_back({{(b[i]==-1)?1e9:b[i], -a[i]}, i});
    sort(v.begin(), v.end());
    for (int i=0; i<=min(cnt, k); i++)
    {
        double res=0;
        vector<double> t;
        for (int j=1; j<=n; j++) if (!c[j]) t.push_back(a[j]);
        sort(t.begin(), t.end());
        for (int j=0; j+1+i<=k; j++) res+=(t[j]/(i+1));
        ans=min(ans, tmp+res);
        if (i!=k) tmp+=(v[i].first.first)/(i+1), c[v[i].second]=1;
    }
    printf("%.10f", 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