Submission #1201895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201895		ofoz	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	737 ms	2460 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>

using namespace std;

int n, k;
vector<int> start, endt;
vector<vector<int>> sm;

double dp(int i, int col, int mxCol, vector<vector<double>>& memo) {
    if (col == mxCol) {
        if (k - i < 0 || k - i > n) return numeric_limits<double>::infinity();
        return static_cast<double>(sm[i][k - i]) / (mxCol + 1);
    }
    if (i == n) return numeric_limits<double>::infinity();

    if (memo[i][col] != -1) return memo[i][col];

    double x = dp(i + 1, col + 1, mxCol, memo) + (static_cast<double>(endt[i]) / (col + 1));
    double y = dp(i + 1, col, mxCol, memo) + (static_cast<double>(start[i]) / (mxCol + 1));

    memo[i][col] = min(x, y);
    return memo[i][col];
}

double f(int col) {
    vector<vector<double>> memo(n + 1);
    for (int i = 0; i <= n; i++) { memo[i] = vector<double>(i+1, -1); }
    return dp(0, 0, col, memo);
}

int main() {
    cin >> n >> k;

    start.resize(n);
    endt.resize(n);

    vector<pair<int, int>> pairs(n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        if (b == -1) b = numeric_limits<int>::max();
        pairs[i] = {a, b};
    }

    sort(pairs.begin(), pairs.end(), [](const pair<int, int>& p1, const pair<int, int>& p2) {
        if (p1.second != p2.second) return p1.second < p2.second;
        return p1.first > p2.first;
    });

    for (int i = 0; i < n; ++i) {
        start[i] = pairs[i].first;
        endt[i] = pairs[i].second;
    }

    sm.assign(n + 1, vector<int>(n + 1, 0));

    for (int i = n - 1; i >= 0; --i) {
        for (int c = 1; c <= n; ++c) {
            if ((n - i) < c) {
                sm[i][c] = numeric_limits<int>::max();
                continue;
            }
            if (i == n - 1) {
                sm[i][c] = start[i];
            } else {
                if (sm[i + 1][c - 1] == numeric_limits<int>::max())
                    sm[i][c] = sm[i + 1][c];
                else
                    sm[i][c] = min(sm[i + 1][c - 1] + start[i], sm[i + 1][c]);
            }
        }
    }

    double res = numeric_limits<double>::infinity();
    int l = 0, r = n;


    for (int mxCol = 0; mxCol <= n; ++mxCol) {
        res = min(res, f(mxCol));
    }

    cout << fixed << res << endl;
    return 0;
}

• 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