Submission #532203

#	Time	Username	Problem	Language	Result	Execution time	Memory
532203		Jarif_Rahman	Let's Win the Election (JOI22_ho_t3)	C++17	56 / 100	2570 ms	226912 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;
    });

    ld ans = 1e9;
    vector<vector<vector<ld>>> dp;

    for(int c = 0; c <= k; c++){
        dp = vector<vector<vector<ld>>>(n, vector<vector<ld>>(c+1, vector<ld>(k-c+1, 1e6)));
        for(int i = 0; i < n; i++) dp[i][0][0] = 0;
        for(int i = n-1; i >= 0; i--){
            for(int j0 = 0; j0 <= c; j0++) for(int j1 = 0; j1 <= k-c && j0+j1 <= n-i; j1++){
                if(j1+j0 == 0) continue;

                if(i == n-1){
                    if(j1 == 1) dp[i][j0][j1] = (ld)v[i].f/(ld)(c+1);
                    else if(j0 == 1 && v[i].sc != -1) dp[i][j0][j1] = (ld)v[i].sc/(ld)c;
                    continue;
                }

                dp[i][j0][j1] = dp[i+1][j0][j1];
                if(j1 != 0) dp[i][j0][j1] = min(dp[i][j0][j1], (ld)v[i].f/(ld)(c+1) + dp[i+1][j0][j1-1]);
                if(v[i].sc != -1 && j0 != 0){
                    dp[i][j0][j1] = min(dp[i][j0][j1], (ld)v[i].sc/(ld)(c-j0+1) + dp[i+1][j0-1][j1]);
                }
            }
        }
        ans = min(ans, dp[0][c][k-c]);
    }

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

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