Submission #885684

#	Time	Username	Problem	Language	Result	Execution time	Memory
885684		boris_mihov	Let's Win the Election (JOI22_ho_t3)	C++17	0 / 100	2584 ms	604 KiB

Main

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 5000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9; 

struct Person
{
    int a, b;
    friend bool operator < (const Person &x, const Person &y)
    {
        if (y.b == -1) return true;
        if (x.b == -1) return false;
        return x.b < y.b;
    }
};

int n, k;
Person p[MAXN];
Person s[MAXN];

void solve()
{
    std::sort(p + 1, p + 1 + n);
    int countColab = 0;
    
    for (int i = 1 ; i <= n ; ++i)
    {
        countColab += (p[i].b != -1);
    }   

    long double ans = INF;
    countColab = std::min(countColab, k);
    assert(countColab == 0);

    for (int colab = 0 ; colab <= countColab ; ++colab)
    {
        long double curr = 0;
        for (int i = 1 ; i <= colab ; ++i)
        {
            curr += (long double)p[i].b / (long double)i;
        }

        for (int i = colab + 1 ; i <= n ; ++i)
        {
            s[i] = p[i];
        }

        std::sort(s + colab + 1, s + n + 1, [&](const Person &x, const Person &y)
        {
            return x.a < y.a;
        });

        for (int i = colab + 1 ; i <= k ; ++i)
        {
            curr += (long double)s[i].a / (long double)(colab + 1);
        }

        ans = std::min(ans, curr);
    }   

    std::cout << std::fixed << std::setprecision(10) << ans << '\n';
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> p[i].a >> p[i].b;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23