Submission #806035

#	Time	Username	Problem	Language	Result	Execution time	Memory
806035		vjudge1	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	1168 ms	8576 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 500;
const ld INF = 1e16;

int n, k;
pair<ld, ld> c[N + 10];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> c[i].first >> c[i].second;
        if(c[i].second == -1) c[i].second = INF;
    }
    sort(c + 1, c + n + 1, [](pair<ld, ld> x, pair<ld, ld> y) {return x.second < y.second;});

    // for(int i = 1; i <= n; i++) 
    //     cout << c[i].first << ' ' << c[i].second << '\n';
    // cout << '\n';
    
    vector<vector<ld>> dp(n + 1, vector<ld>(n + 1, INF));
    dp[0][1] = 0;
    for(int i = 1; i <= n; i++) {
        vector<vector<ld>> newdp = dp;
        for(int k = 1; k <= i; k++) {
            for(int v = 1; v <= i + 1; v++) {
                newdp[k][v] = min(newdp[k][v], dp[k - 1][v] + c[i].first / v); 
                if(v > 1 && c[i].second != INF) 
                    newdp[k][v] = min(newdp[k][v], dp[k - 1][v - 1] + c[i].second / (v - 1)) ;
            }
        }
        dp = newdp;
        // for(int k = 1; k <= n; k++) {
        //     for(int v = 1; v <= n; v++) {
        //         cout <<setprecision(1) << fixed << dp[k][v] << ' ';
        //     }
        //     cout << '\n';
        // }
        // cout << '\n';
    }
    ld res = INF;
    for(int v = 1; v <= n; v++) {
        res = min(res, dp[k][v]);
    }
    cout << setprecision(9) << fixed << res ;
}   

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