Submission #1141085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141085		hennessey	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	1234 ms	4472 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ld long double
vector <pair <ld, ld>> arr = {};
// vector <pair <ld, ld>> arr = {};
vector <ld> minvs(502);
vector <int> cntin(1002);
// int sum = 0;
vector <vector <ld>> dp(502, vector <ld> (502, -1));
ld dps(int cur, int ck, int k, int cuk, int n) {
    if(cuk == ck) {
        ld a = ck+1;
        return minvs[cur]/a;
    }
    if(cur == k) {
        return 1e18;
    }
    if(dp[cur][cuk] != -1) {
        return dp[cur][cuk];
    }
    // int totalm = 1e18;
    ld a = cuk+1;
    ld data = dps(cur+1, ck, k, cuk+1, n)+(arr[cur].second/a);
    a = ck+1;
    ld data2 = dps(cur+1, ck, k, cuk, n)+(arr[cur].first/a);
    return dp[cur][cuk] = min(data, data2);
}

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});
        // arr2.push_back({a, b});
    }
    sort(arr.begin(), arr.end(), [&](auto& left, auto& right) {
        return left.second < right.second;
    });
    // sort(arr2.begin(), arr2.end(), [&](auto& left, auto& right) {
    //     return left.first < right.first;
    // });
    // for(int i = 0; i < k; i++) {
    //     sum += arr2[i].first;
    //     cntin[arr2[i].first] = i+1;
    // }
    // for(int i = 0; i < n; i++) {
    //     cout << arr[i].first << " " << arr[i].second << endl;
    // }
    ld sum = 0;
    vector <ld> ar = {};
    for(int i = k; i < n; i++) {
        ar.push_back(arr[i].first);
    }
    sort(ar.begin(), ar.end());
    int ch = 0;
    for(int i = k; i >= 0; i--) {
        // cout << "HELLO" << endl;
        sum = 0;
        if(ar.size() == 0) {
            if(i == 0) {
                break;
            }
            ld v2 = arr[i-1].first;
            ar.push_back(v2);
            continue;
        }
        // auto it = ar.begin();
        // ld v = *it;
        // sum += v;
        // ar.erase(it);
        for(int j = 0; j < ((k-i)); j++) {
            sum += ar[j];
        }
        minvs[i] = sum;
        if(i == 0) {
            break;
        }
        ld v2 = arr[i-1].first;
        ar.push_back(v2);
        sort(ar.begin(), ar.end());
    }
    // for(int i = 0; i <= k; i++) {
    //     cout << minvs[i] << " ";
    // }
    // cout << 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++) {
                dp[i][j] = -1;
            }
        }
        ld data = dps(0, i, k, 0, n);
        totalm = min(totalm, data);
        // if(i == 0) {
        //     cout << data << " " << totalm << endl;
        // }
        // cout << data << endl;
    }
    cout << totalm << endl;
    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