oj.uz

Submission #922069

# Submission time Handle Problem Language Result Execution time Memory
922069 2024-02-05T01:29:47 Z cthbst Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 1604 ms 2644 KB 
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

const int maxn = 505;
const double INF = 1e18;

int n, k;
double a[maxn];
double b[maxn];
pair<double, double> p[maxn];
double dp[maxn][maxn];

double f(int s, int cnt) {
    vector<double> v;
    for (int i = s; i < n; i++) {
        v.push_back(a[i]);
    }
    if ((int)v.size() < cnt) return INF;
    sort(v.begin(), v.end());
    double rtn = 0;
    for (int i = 0; i < cnt; i++) {
        rtn += v[i];
    }
    return rtn;
}

double myDP(int x) {
    dp[0][0] = a[0] / (x + 1);
    dp[0][1] = b[0] / 1;
    for (int j = 2; j <= x; j++) dp[0][j] = INF;

    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + a[i] / (x + 1);
        for (int j = 1; j <= x; j++) {
            if (j > i + 1) {
                dp[i][j] = INF;
            } else {
                double A = dp[i - 1][j] + a[i] / (x + 1);
                double B = dp[i - 1][j - 1] + b[i] / j;
                dp[i][j] = min(A, B);
            }
        }
    }

    double rtn = INF;
    for (int i = 0; i < n; i++) {
        rtn = min(rtn, dp[i][x] + f(i + 1, k - x) / (x + 1));
    }
    // cout << "solve(" << x << ") = " << rtn << '\n';
    return rtn;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        if (b[i] == -1) b[i] = INF;
        p[i] = {b[i], a[i]};
    }
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        b[i] = p[i].first;
        a[i] = p[i].second;
    }
    double an = f(0, k);
    for (int x = 1; x <= k; x++) {
        an = min(an, myDP(x));
    }
    cout << fixed << setprecision(15) << an << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 59 ms 2396 KB Output is correct
6 Correct 148 ms 2396 KB Output is correct
7 Correct 302 ms 2436 KB Output is correct
8 Correct 427 ms 2432 KB Output is correct
9 Correct 525 ms 2640 KB Output is correct
10 Correct 297 ms 2428 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 59 ms 2396 KB Output is correct
6 Correct 148 ms 2396 KB Output is correct
7 Correct 302 ms 2436 KB Output is correct
8 Correct 427 ms 2432 KB Output is correct
9 Correct 525 ms 2640 KB Output is correct
10 Correct 297 ms 2428 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 188 ms 2432 KB Output is correct
13 Correct 337 ms 2432 KB Output is correct
14 Correct 264 ms 2396 KB Output is correct
15 Correct 396 ms 2432 KB Output is correct
16 Correct 756 ms 2436 KB Output is correct
17 Correct 726 ms 2432 KB Output is correct
18 Correct 518 ms 2436 KB Output is correct
19 Correct 941 ms 2640 KB Output is correct
20 Correct 740 ms 2644 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1604 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 59 ms 2396 KB Output is correct
6 Correct 148 ms 2396 KB Output is correct
7 Correct 302 ms 2436 KB Output is correct
8 Correct 427 ms 2432 KB Output is correct
9 Correct 525 ms 2640 KB Output is correct
10 Correct 297 ms 2428 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 188 ms 2432 KB Output is correct
13 Correct 337 ms 2432 KB Output is correct
14 Correct 264 ms 2396 KB Output is correct
15 Correct 396 ms 2432 KB Output is correct
16 Correct 756 ms 2436 KB Output is correct
17 Correct 726 ms 2432 KB Output is correct
18 Correct 518 ms 2436 KB Output is correct
19 Correct 941 ms 2640 KB Output is correct
20 Correct 740 ms 2644 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Halted 0 ms 0 KB -