Submission #800547

#	Time	Username	Problem	Language	Result	Execution time	Memory
800547		caganyanmaz	Let's Win the Election (JOI22_ho_t3)	C++17	33 / 100	490 ms	814956 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;
}


constexpr static int MXSIZE2 = 101;
double dp[MXSIZE2][MXSIZE2][MXSIZE2][MXSIZE2]; // Position, expected value, filled count, current value
array<int, 2> v[MXSIZE2];
void subtask2()
{
        cin >> k;
        for (int i = 0; i < n; i++)
        {
                int aa, bb;
                cin >> aa >> bb;
                bb = (bb == -1) ? INF : bb;
                v[i] = mp(bb, aa);
        }
        for (int i = 0; i < MXSIZE2; i++)
                for (int j = 0; j < MXSIZE2; j++)
                        for (int l = 0; l < MXSIZE2; l++)
                                for (int w = 0; w < MXSIZE2; w++)
                                        if (w != 0 || l != 0)
                                                dp[i][j][l][w] = INF;
        sort(v, v + n);
        for (int i = n-1; i >= 0; i--)
        {
                double bb = v[i][0], aa = v[i][1];
                for (int j = 0; j <= k; j++)
                {
                        for (int l = 0; l <= k; l++)
                        {
                                for (int w = 0; w <= j; w++)
                                {
                                        dp[i][j][l][w] = dp[i+1][j][l][w];
                                        if (l != 0)
                                                dp[i][j][l][w] = min({dp[i][j][l][w], (w > 0) ? (dp[i+1][j][l-1][w-1] + (bb / (j-w+1))) : INF, dp[i+1][j][l-1][w] + (aa / (j+1))} );
                                }
                        }
                }
        }
        double best = INF;
        for (int i = 0; i <= n; i++)
                best = min(best, dp[0][i][k][i]);

        cout << fixed;
        cout << setprecision(20);
        cout << best << "\n";


}

int main()
{
        cin >> n;
        if (n < 100)
        {
                subtask2();
                return 0;
        }
        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: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23