oj.uz

Submission #885684

# Submission time Handle Problem Language Result Execution time Memory
885684 2023-12-10T13:01:23 Z boris_mihov Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 2500 ms 604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2584 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2584 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2584 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -