oj.uz

Submission #641170

# Submission time Handle Problem Language Result Execution time Memory
641170 2022-09-16T06:48:13 Z cthbst Let's Win the Election (JOI22_ho_t3) C++14
21 / 100
 965 ms 8404 KB 
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

#define int long long
using pdd = pair<long double, long double>;

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

int n, k;
vector<pdd> vc;
long double dp[maxn][maxn];
long double sf[maxn][maxn];  // sf[i][j] 從 A[i~(n-1)] 選 j 個最小的數字

void build_sf() {
    for (int i = 1; i < maxn; i++) {
        fill(sf[i] + 1, sf[i] + maxn, INF);
    }

    for (int i = n - 1; i >= 0; i--) {
        vector<long double> cur;
        for (int j = i; j < n; j++) {
            cur.push_back(vc[j].first);
        }
        sort(cur.begin(), cur.end());
        sf[i][0] = 0;
        for (int j = 1; j <= k; j++) {
            if (j > (int)(cur.size()))
                break;
            else
                sf[i][j] = sf[i][j - 1] + cur[j - 1];
        }
    }
}

long double solve(const int t) {
    for (int i = 0; i < n; i++) {
        fill(dp[i], dp[i] + (t + 1), INF);
    }

    for (int i = 0; i < n; i++) {
        if (i == 0) {
            dp[i][0] = vc[i].first / (t + 1.0);
            dp[i][1] = vc[i].second;
            continue;
        }
        for (int j = 0; j <= t; j++) {
            if (j == 0) {
                dp[i][0] = dp[i - 1][0] + vc[i].first / (t + 1.0);
            } else {
                long double x = dp[i - 1][j] + vc[i].first / (t + 1.0);
                long double y = dp[i - 1][j - 1] + vc[i].second * 1.0 / j;
                dp[i][j] = min(x, y);
            }
        }
    }
    if (k == n) {
        return dp[n - 1][t];
    }
    long double res = sf[0][k];
    for (int i = t - 1; i < n - k + t; i++) {
        res = min(res, dp[i][t] + sf[i + 1][k - t] / (t + 1.0));
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (y == -1) {
            vc.push_back({x, INF});
        } else {
            vc.push_back({x, y});
        }
    }
    sort(vc.begin(), vc.end(),
         [](pdd a, pdd b) { return a.second < b.second; });
    build_sf();

    long double res = sf[0][k];
    for (int t = 1; t <= k; t++) {
        res = min(res, solve(t));
    }
    cout << res << '\n';

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 4 ms 4296 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 23 ms 6656 KB Output is correct
6 Correct 71 ms 7176 KB Output is correct
7 Correct 238 ms 8296 KB Output is correct
8 Correct 496 ms 8324 KB Output is correct
9 Correct 965 ms 8296 KB Output is correct
10 Correct 471 ms 8272 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 4 ms 4296 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 23 ms 6656 KB Output is correct
6 Correct 71 ms 7176 KB Output is correct
7 Correct 238 ms 8296 KB Output is correct
8 Correct 496 ms 8324 KB Output is correct
9 Correct 965 ms 8296 KB Output is correct
10 Correct 471 ms 8272 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 89 ms 7428 KB Output is correct
13 Correct 95 ms 7392 KB Output is correct
14 Correct 95 ms 7484 KB Output is correct
15 Correct 440 ms 8176 KB Output is correct
16 Correct 467 ms 8372 KB Output is correct
17 Correct 442 ms 8296 KB Output is correct
18 Correct 869 ms 8376 KB Output is correct
19 Correct 910 ms 8324 KB Output is correct
20 Correct 878 ms 8220 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 901 ms 8296 KB Output is correct
2 Correct 918 ms 8404 KB Output is correct
3 Correct 879 ms 8264 KB Output is correct
4 Correct 876 ms 8256 KB Output is correct
5 Correct 881 ms 8328 KB Output is correct
6 Correct 898 ms 8400 KB Output is correct
7 Correct 869 ms 8296 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4308 KB Output is correct
2 Correct 3 ms 4308 KB Output is correct
3 Correct 4 ms 4296 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 23 ms 6656 KB Output is correct
6 Correct 71 ms 7176 KB Output is correct
7 Correct 238 ms 8296 KB Output is correct
8 Correct 496 ms 8324 KB Output is correct
9 Correct 965 ms 8296 KB Output is correct
10 Correct 471 ms 8272 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 89 ms 7428 KB Output is correct
13 Correct 95 ms 7392 KB Output is correct
14 Correct 95 ms 7484 KB Output is correct
15 Correct 440 ms 8176 KB Output is correct
16 Correct 467 ms 8372 KB Output is correct
17 Correct 442 ms 8296 KB Output is correct
18 Correct 869 ms 8376 KB Output is correct
19 Correct 910 ms 8324 KB Output is correct
20 Correct 878 ms 8220 KB Output is correct
21 Correct 4 ms 4308 KB Output is correct
22 Correct 4 ms 4308 KB Output is correct
23 Correct 4 ms 4308 KB Output is correct
24 Correct 4 ms 4296 KB Output is correct
25 Correct 3 ms 4308 KB Output is correct
26 Correct 4 ms 4308 KB Output is correct
27 Correct 4 ms 4308 KB Output is correct
28 Correct 4 ms 4308 KB Output is correct
29 Incorrect 3 ms 4296 KB Output isn't correct
30 Halted 0 ms 0 KB -