Submission #936312

#	Time	Username	Problem	Language	Result	Execution time	Memory
936312		qwe1rt1yuiop1	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	879 ms	998832 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;
    }
    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;

    cout << fixed << setprecision(10);

    vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(n + 1, vector<double>(n + 2, 1e15)));
    dp[0][0][1] = 0;
    for (int i = 0; i < n; ++i)
    {
        dp[i + 1] = dp[i];
        for (int j = 0; j < n; ++j)
            for (int k = 1; k < n + 2; ++k)
            {
                dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + 1.0 * a[i] / k);
                if (b[i] != -1 && k != n + 1)
                    dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + 1.0 * b[i] / k);
            }
    }
    double ans = 1e15;
    for (int i = 0; i <= n; ++i)
        for (int j = kk; j <= kk; ++j)
            for (int k = 0; k < n + 2; ++k)
                ans = min(ans, dp[i][j][k]);
    assert(ans < 1e14);
    cout << ans << '\n';
    // for (auto i : dp[n])
    // {
    //     for (auto j : i)
    //         cout << j << ' ';
    //     cout << '\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)
      |                ^
Main.cpp:18:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto &[b, a] : v)
      |                ^

• 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