제출 #1257972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257972		chikien2009	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct FENWICK_TREE
{
    int num[501], tree[501];
    inline void Update(int x, int v, int o)
    {
        while (x <= 500)
        {
            tree[x] += v * o;
            num[x] += o;
            x += (x & (~(x - 1)));
        }
    }
    inline int Get(int v)
    {
        int res = 0, x = 0;
        for (int i = 10; i >= 0; --i)
        {
            if (x + (1 << i) <= 500 && num[x + (1 << i)] <= v)
            {
                x += (1 << i);
                res += tree[x];
                v -= num[x];
            }
        }
        return res;
    }
} ft;

int n, m;
double res = 0, sum;
array<int, 3> p[500];

int main()
{
    setup();

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    {
        cin >> p[i][0] >> p[i][1];
        p[i][1] = (p[i][1] == -1 ? 2000 : p[i][1]);
    }
    sort(p, p + n);
    for (int i = 0; i < n; ++i)
    {
        res += p[i][0] * (i < m);
        p[i][2] = i + 1;
        ft.Update(p[i][2], p[i][0], 1);
        swap(p[i][0], p[i][1]);
    }
    sort(p, p + n);
    for (int i = 0; i < m; ++i)
    {
        if (p[i][0] == 2000)
        {
            break;
        }
        sum += (double)p[i][0] / (i + 1);
        ft.Update(p[i][2], p[i][1], -1);
        res = min(res, sum + (double)ft.Get(m - i - 1) / (i + 2));
    }
    cout << fixed << setprecision(6) << res;
    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