Submission #636965

#	Time	Username	Problem	Language	Result	Execution time	Memory
636965		danikoynov	Let's Win the Election (JOI22_ho_t3)	C++14	100 / 100	518 ms	4436 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[maxn][maxn], 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;

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));
            }
        }


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

        for (int i = 0; i <= k; i ++)
        {
            double sum = fp[i][goal] + dp[i + 1][k - i];
            if (sum < ans)
                ans = sum;
        }
        ///ans = min(ans, fp[n][goal]);
    }

    printf("%0.6f\n", ans);
}

int main()
{
    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