Submission #636963

#	Time	Username	Problem	Language	Result	Execution time	Memory
636963		danikoynov	Let's Win the Election (JOI22_ho_t3)	C++14	67 / 100	183 ms	10964 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 510, smalln = 110;
struct city
{
    int a, b, idx;
}c[maxn], ct[maxn];
int n, k, used[maxn];

bool cmpa(city c1, city c2)
{
    return c1.a < c2.a;
}
bool cmpb(city c1, city c2)
{
    if (c1.b != -1 && c2.b != -1)
        return c1.b < c2.b;
    if (c1.b != -1)
        return true;
    if (c2.b != -1)
        return false;
    return c1.idx < c2.idx;
}

double dp[smalln][smalln][smalln], fp[maxn][maxn];
/// dp[i][j][f] - smallest time up to the i-th city using j votes and f collaborators
void solve()
{
    cin >> n >> k;
    int col = 0;
    for (int i = 1; i <= n; i ++)
    {
        cin >> c[i].a >> c[i].b;
        if (c[i].b != -1)
            col ++;
        c[i].idx = i;
        ct[i] = c[i];
    }

    sort(c + 1, c + n + 1, cmpb);
    double ans = 1e18;
    if (k != n)
    {


    for (int goal = 0; goal <= min(k, col); goal ++)
    {
        for (int i = 0; i <= n; i ++)
            for (int j = 0; j <= k; j ++)
            for (int f = 0; f <= goal; f ++)
            dp[i][j][f] = 1e18;

        dp[0][0][0] = 0.0;
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j <= k; j ++)
            for (int f = 0; f <= goal; f ++)
        {
            dp[i][j][f] = dp[i - 1][j][f];
            if (j >= 1)
            {
                dp[i][j][f] = min(dp[i][j][f], dp[i - 1][j - 1][f] + c[i].a / (double)(goal + 1.0));
            }
            if (f >= 1 && c[i].b != -1 && j >= 1)
            {
                dp[i][j][f] = min(dp[i][j][f], dp[i - 1][j - 1][f - 1] + c[i].b / (double)(f));
            }
        }

        /**cout << "--------- " << goal << " -------------------" << endl;
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j <= k; j ++)
            for (int f = 0; f <= goal; f ++)
            cout << i << " " << j << " " << f << " " << dp[i][j][f] << endl;*/

        ans = min(ans, dp[n][k][goal]);
    }
    }
    else

    {
for (int goal = 0; goal <= min(k, col); goal ++)
    {
        for (int i = 0; i <= n; i ++)
            for (int f = 0; f <= goal; f ++)
            fp[i][f] = 1e18;

        fp[0][0] = 0.0;
        for (int i = 1; i <= n; i ++)
            for (int f = 0; f <= goal; f ++)
        {
                fp[i][f] = min(fp[i][f], fp[i - 1][f] + c[i].a / (double)(goal + 1.0));

            if (f >= 1 && c[i].b != -1)
            {
                fp[i][f] = min(fp[i][f], fp[i - 1][f - 1] + c[i].b / (double)(f));
            }
        }

        /**cout << "--------- " << goal << " -------------------" << endl;
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j <= k; j ++)
            for (int f = 0; f <= goal; f ++)
            cout << i << " " << j << " " << f << " " << fp[i][j][f] << endl;*/

        ans = min(ans, fp[n][goal]);
    }
    }
    printf("%0.6f\n", ans);
}

int main()
{
    solve();
    return 0;
}

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