Submission #1183971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183971		jerzyk	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	1296 ms	8344 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 503;
pair<int, int> tab[N];
ld dp[N][N], dp2[N][N];

ld LiczDP(int n, int k, int l)
{
    //cout << fixed << setprecision(7) << "DP: " << l << "\n";
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= k; ++j)
            {dp[i][j] = II; dp2[i][j] = II;}
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 0; j <= l; ++j)
        {
            dp[i][j] = dp[i - 1][j] + (ld)tab[i].nd / (ld)(l + 1);
            if(j > 0)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (ld)tab[i].st / (ld)j);
            //cout << i << " " << j << " " << dp[i][j] << "\n";
        }
    for(int i = l; i <= n; ++i)
    {
        dp2[i][i - l] = dp[i][l];
        //cout << "C: " << i << " " << dp2[i][k - l] << "\n";
        for(int j = 0; j <= k - l && i > 0; ++j)
        {
            dp2[i][j] = min(dp2[i][j], dp2[i - 1][j]);
            if(j > 0)
                dp2[i][j] = min(dp2[i][j], dp2[i - 1][j - 1] + (ld)tab[i].nd / (ld)(l + 1));
        }
        //cout << "C: " << i << " " << dp2[i][k - l] << "\n";
    }
    return dp2[n][k - l];
}

void Solve()
{
    cout << fixed << setprecision(7);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
    {
        cin >> tab[i].nd >> tab[i].st;
        if(tab[i].st == -1) tab[i].st = II;
    }
    sort(tab + 1, tab + 1 + n);
    ld ans = II;
    //cout << "T:\n";
    //for(int i = 1; i <= n; ++i)
        //cout << tab[i].st << " " << tab[i].nd << "\n";
    for(int i = 0; i < k; ++i)
        ans = min(ans, LiczDP(n, k, i));

    cout << fixed << setprecision(7) << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

• 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