Submission #1140895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140895		hennessey	Let's Win the Election (JOI22_ho_t3)	C++17	56 / 100	669 ms	17608 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ld long double
vector <pair <ld, ld>> arr = {};
vector <vector <vector <ld>>> dp(102, vector <vector <ld>>(102, vector <ld>(102, -1)));
ld dps(int cur, int n, int k, int ck, int cuk, int cak) {
    if(cur == n) {
        if((cuk+cak) == k && ck == cuk) {
            return 0;
        }
        return 1e18;
    }
    if(dp[cur][cuk][cak] != -1) {
        return dp[cur][cuk][cak];
    }
    ld totalm = 1e18;
    if(cuk < ck) {
        ld a = cuk+1;
        ld data = dps(cur+1, n, k, ck, cuk+1, cak)+(arr[cur].second/(a));
        // if(ck == 1 && cur == 0) {
        //     // cout << a << " " << data << " " << totalm << " " << arr[cur].second << endl;
        // }
        totalm = min(totalm, data);
    }
    if((cuk+cak) < k) {
        ld a = ck+1;
        ld data = dps(cur+1, n, k, ck, cuk, cak+1)+(arr[cur].first/a);
        // if(ck == 1 && cuk == 1 && cur == 1) {
        //     cout << a << " " << data << " " << cak << " " << arr[cur].second << " " << totalm << endl;
        // }
        totalm = min(totalm, data);
    }
    ld data = dps(cur+1, n, k, ck, cuk, cak);
    totalm = min(totalm, data);
    return dp[cur][cuk][cak] = totalm;
}

signed main() {
    //your code goes here
    int n;
    cin >> n;
    int k;
    cin >> k;
    for(int i = 0; i < n; i++) {
        ld a, b;
        cin >> a >> b;
        if(b == -1) {
            b = 1e18;
        }
        arr.push_back({a, b});
    }
    sort(arr.begin(), arr.end(), [&](auto& left, auto& right) {
        return left.second < right.second;
    });
    // for(int i = 0; i < n; i++) {
    //     cout << arr[i].first << " " << arr[i].second << endl;
    // }
    ld totalm = 1e18;
    for(int i = 0; i <= k; i++) {
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= k; j++) {
                for(int l = 0; l <= k; l++) {
                    dp[i][j][l] = -1;
                }
            }
        }
        ld data = dps(0, n, k, i, 0, 0);
        totalm = min(totalm, data);
        // cout << data << endl;
    }
    cout << totalm << endl;
    return 0;
}

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