Submission #1208436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208436		dima2101	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	659 ms	4388 KiB

Main

#include <bits/stdc++.h>
#define int long long

const int MAXN = 502;
long double dp[MAXN][MAXN];

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, k;
    std::cin >> n >> k;

    std::vector<std::pair<int, int>> all(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> all[i].first >> all[i].second;
        if (all[i].second == -1)
        {
            all[i].second = 1e13;
        }
    }
    std::sort(all.begin(), all.end(), [&](std::pair<int, int> a, std::pair<int, int> b)
              { return a.second < b.second; });
    long double min = 1e18;
    for (int i = 0; i <= k; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int z = 0; z <= n; z++)
            {
                dp[j][z] = 1e9;
            }
        }
        dp[0][0] = 0;
        for (int j = 1; j <= n; j++)
        {
            for (int z = 0; z <= std::min(k - i, j); z++)
            {
                int first = std::min((j - z), i);
                if (z > 0)
                {
                    dp[j][z] = std::min(dp[j][z], dp[j - 1][z - 1] + (long double)(all[j - 1].first) / (long double)(i + 1));
                }
                if ((j - 1 - z) < i)
                {
                    dp[j][z] = std::min(dp[j][z], dp[j - 1][z] + (long double)(all[j - 1].second) / (long double)(first));
                }
                else
                {
                    dp[j][z] = std::min(dp[j][z], dp[j - 1][z]);
                }
                // std::cout << dp[j][z] << ' ' << j << ' ' << z << ' ' << std::min(k - i, j) << std::endl;
            }
        }
        // std::cout << dp[n][k - i] << std::endl;

        min = std::min(min, dp[n][k - i]);
    }
    std::cout << std::setprecision(10) << std::fixed << min;
}

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