Submission #526875

#	Time	Username	Problem	Language	Result	Execution time	Memory
526875		eecs	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	914 ms	2376 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxn = 510;
int n, K, b;
double f[maxn][maxn];
array<int, 2> a[maxn];

void chk(double &x, double y) {
    if (x > y) x = y;
}

int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i][1], &a[i][0]);
        if (~a[i][0]) b++;
    }
    sort(a + 1, a + n + 1);
    auto calc = [&](int num) {
        for (int i = 0; i <= n; i++) {
            fill(f[i], f[i] + n + 1, 1e18);
        }
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = min(i, num); ~j; j--) {
                for (int k = i - j; ~k; k--) {
                    if (~a[i + 1][0]) chk(f[j + 1][k], f[j][k] + 1.0 * a[i + 1][0] / (j + 1));
                    chk(f[j][k + 1], f[j][k] + 1.0 * a[i + 1][1] / (num + 1));
                }
            }
        }
        return f[num][K - num];
    };
    int l = 0, r = min(b, K);
    while (l < r) {
        int mid = (l + r) / 2;
        calc(mid) > calc(mid + 1) ? l = mid + 1 : r = mid;
    }
    printf("%.9f\n", calc(l));
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d %d", &n, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d %d", &a[i][1], &a[i][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