Submission #532207

#	Time	Username	Problem	Language	Result	Execution time	Memory
532207		Jarif_Rahman	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	427 ms	4712 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
typedef double ld;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cerr.precision(100);
    cout.precision(100);

    int n, k; cin >> n >> k;
    vector<pair<int, int>> v(n);
    for(auto &p: v) cin >> p.f >> p.sc;

    sort(v.begin(), v.end(), [](pair<ld, ld> a, pair<ld, ld> b){
        swap(a.f, a.sc);
        swap(b.f, b.sc);
        if(a.f == -1) a.f = 1e9;
        if(b.f == -1) b.f = 1e9;
        return a < b;
    });

    vector<vector<ld>> last(n, vector<ld>(n+1, 1e6));
    for(int i = 0; i < n; i++) last[i][0] = 0;

    for(int c = 1; c <= n; c++){
        priority_queue<int> pq;
        int s = 0;
        for(int i = n-1; i >= n-c; i--) pq.push(v[i].f), s+=v[i].f;
        last[n-c][c] = s;
        for(int i = n-c-1; i >= 0; i--){
            if(v[i].f < pq.top()) s-=pq.top(), pq.pop(), pq.push(v[i].f), s+=v[i].f;
            last[i][c] = s;
        }
    }

    ld ans = last[0][k];

    for(int c = 0; c <= k; c++){
        vector<vector<ld>> dp(n, vector<ld>(c+1, 1e6));
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= min(i+1, c); j++){
                if(i == 0){
                    if(j == 0) dp[i][j] = ld(v[i].f)/ld(c+1);
                    else if(j == 1 && v[i].sc != -1) dp[i][j] = v[i].sc;
                    continue;
                }

                if(i >= j)
                    dp[i][j] = min(dp[i][j], dp[i-1][j]+ld(v[i].f)/ld(c+1));

                if(v[i].sc != -1 && j > 0)
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+ld(v[i].sc)/ld(j));
            }
        }

        for(int i = 0; i < k; i++)
            ans = min(ans, dp[i][c] + (i == n-1 ? 0.0 : last[i+1][k-i-1]/ld(c+1)));
    }

    cout << ans << "\n";
}

• 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