Submission #1319721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319721		Ghulam_Junaid	Let's Win the Election (JOI22_ho_t3)	C++20	0 / 100	5 ms	5172 KiB

Main

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

typedef long double ld;

const int N = 505;
int n, k, a[N], b[N], par[N][N];
vector<pair<int, int>> vec;
ld dp[N][N];

int main(){
    cin >> n >> k;
    int sm = 0;
    for (int i = 0; i < n; i ++){
        cin >> a[i] >> b[i];
        if (b[i] == -1)
            b[i] = 1e6;
        sm += a[i];
        vec.push_back({b[i], -a[i]});
    }
    sort(vec.begin(), vec.end());

    for (int i = 0; i < n; i ++)
        a[i] = -vec[i].second, b[i] = vec[i].first;

    for (int i = 0; i <= n; i ++){
        for (int j = 0; j <= n; j ++){
            if (j == 0)
                dp[i][j] = sm;
            else if (i == 0)
                dp[i][j] = 1e6;
            else{
                dp[i][j] = 1e6;
                if (dp[i - 1][j] < dp[i][j])
                    par[i][j] = j, dp[i][j] = dp[i - 1][j];
                if (dp[i - 1][j - 1] + (ld)b[i - 1] / (ld)j - a[i - 1] < dp[i][j]);
                    par[i][j] = j - 1, dp[i][j] = dp[i - 1][j - 1] + (ld)b[i - 1] / (ld)j - a[i - 1];
            }
        }
    }

    ld ans = 1e6;
    for (int i = 0; i <= n; i ++){
        vector<int> inds;
        int ci = n, cj = i;
        while (cj > 0){
            if (cj != par[ci][cj])
                inds.push_back(ci - 1);
            cj = par[ci][cj];
            ci--;
        }
        reverse(inds.begin(), inds.end());
        
        ld tme = 0; int cur = 1, csm = sm;
        for (int j : inds){
            tme += (ld)b[j] / (ld)cur;
            cur++; 
            csm -= a[j];
        }
        tme += (ld)csm / (ld)cur;
        ans = min(ans, tme);
    }

    cout.precision(20);
    cout << ans << endl;
}

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