Submission #936310

#	Time	Username	Problem	Language	Result	Execution time	Memory
936310		qwe1rt1yuiop1	Let's Win the Election (JOI22_ho_t3)	C++14	56 / 100	2555 ms	112520 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int, int>;

void solve()
{
    int n, kk;
    cin >> n >> kk;
    vector<pii> v(n);
    for (auto &[b, a] : v)
    {
        cin >> a >> b;
        if (b == -1)
            b = INT_MAX;
    }
    cout << fixed << setprecision(5);
    sort(v.begin(), v.end());
    // for (auto &[b, a] : v)
    //     if (b == INT_MAX)
    //         b = -1;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i)
        a[i] = v[i].second, b[i] = v[i].first;

    double ans = 1e15;
    for (int goal = 1; goal <= kk + 1; ++goal)
    {
        vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(kk + 1, vector<double>(goal + 1, 1e15)));
        dp[0][0][1] = 0;
        for (int i = 0; i < n; ++i)
        {
            dp[i + 1] = dp[i];
            for (int j = 0; j < kk; ++j)
            {
                for (int k = 1; k <= goal; ++k)
                {
                    dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + 1.0 * a[i] / goal);
                    if (k != goal)
                        dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + 1.0 * b[i] / k);
                }
            }
        }
        ans = min(ans, dp[n][kk][goal]);
    }
    cout << ans << '\n';
}

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

    solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:11:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |     for (auto &[b, a] : v)
      |                ^

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