Submission #800438

#	Time	Username	Problem	Language	Result	Execution time	Memory
800438		caganyanmaz	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	1 ms	304 KiB

Main

#include <bits/stdc++.h>
//#define double  long double
#define mp(x...) array<int, 2>({x})
using namespace std;

constexpr static int INF = 1e8;
constexpr static int MXSIZE = 1000;
bitset<MXSIZE> added;
array<int, 2> a[MXSIZE];
array<int, 3> b[MXSIZE];
int n, k;

double calculate(int cc)
{
        int count = 0;
        double cost = 0;
        for (int i = 0; i < cc; i++)
        {
                cost += static_cast<double>(b[i][0]) / (i+1);
                count++;
        }
        for (int i = 0; i < n && count < k; i++)
        {
                if (added[a[i][1]])
                        continue;
                cost += static_cast<double>(a[i][0]) / (cc+1);
                count++;
        }
        assert(count == k);
        return cost;
}

int main()
{
        cin >> n;
        cin >> k;
        for (int i = 0; i < n; i++)
        {
                int aa, bb;
                cin >> aa >> bb;
                a[i] = mp(aa, i);
                bb = bb == -1 ? INF : bb;
                b[i] = array<int, 3>({bb, -aa, i});
        }
        sort(a, a + n);
        sort(b, b + n);
        double best = INF;
        for (int i = 0; i <= k && (i == 0 || b[i-1][0] != INF); i++)
        {
                if (i > 0)
                        added[b[i-1][2]] = true;
                best = min(best, calculate(i));
        }
        cout << fixed;
        cout << setprecision(20);
        cout << best << "\n";

}

• 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