Submission #1266638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266638		nguyn	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	100 ms	448 KiB

Main

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

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

pii a[505];
int n, m;
double res = 1e9;

bool cmp(pii x, pii y) {
    if (x.F != y.F) return x.F < y.F;
    return x.S < y.S;
}

double f[505];

void cal(int k) {
    for (int i = 0; i <= n; i++) {
        f[i] = 1e9;
    }
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
//        cout << a[i].F << ' ' << a[i].S << endl;
        for (int j = m - k; j >= 0; j--) {
            if (j < m - k) {
                f[j + 1] = min(f[j + 1], f[j] + (double)a[i].S / (k + 1));
            }
            int x = i - j;
            if (0 < x && x <= k) f[j] += (double)a[i].F / x;
        }
    }
//    cout << f[n][k] << endl;
//    cout << f[m - k] << endl;
    res = min(res, f[m - k]);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].S >> a[i].F;
        if (a[i].F == -1) a[i].F = 1e9;
    }
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 0; i < m; i++) {
        cal(i);
    }
    cout << fixed << setprecision(20) << res;
}

• 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