Submission #806234

#	Time	Username	Problem	Language	Result	Execution time	Memory
806234		vjudge1	Let's Win the Election (JOI22_ho_t3)	C++17	33 / 100	1166 ms	8536 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];
bool is1Subtask = 1;

ll w[(1 << 20)][20];

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;
        is1Subtask &= (c[i].second == c[i].first || c[i].second == INF);
    }
    sort(c + 1, c + n + 1, [](pair<ld, ld> x, pair<ld, ld> y) {return x.second < y.second;});
    if(is1Subtask) {
        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;
        }
        ld res = INF;
        for(int v = 1; v <= n; v++) {
            res = min(res, dp[k][v]);
        }
        cout << setprecision(9) << fixed << res ;
        return 0;
    }
    if(n <= 20) {
        ld res = INF;
        for(int msk = 0; msk < (1 << n); msk++) {
            vector<ll> v;
            vector<ll> w(n + 1, -1);
            ld sum = 0, veloc = 1;
            for(int i = 0; i < n; i++) {
                if(msk >> i & 1) {
                    sum += c[i + 1].second / veloc;
                    veloc++;
                } else {
                    v.push_back(c[i + 1].first);
                }
            }
            sort(v.begin(), v.end());
            for(int i = 0; i <= k - veloc; i++) 
                sum += v[i] / veloc;
            res = min(res, sum);
        }
        cout << setprecision(9) << fixed << res ;
        return 0;
    }
}  

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