oj.uz

Submission #641115

# Submission time Handle Problem Language Result Execution time Memory
641115 2022-09-16T02:32:44 Z cthbst Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 946 ms 8424 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);
            }
        }
    }
    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 4 ms 4308 KB Output is correct
2 Correct 4 ms 4308 KB Output is correct
3 Correct 4 ms 4320 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 24 ms 6672 KB Output is correct
6 Correct 81 ms 7224 KB Output is correct
7 Correct 233 ms 8256 KB Output is correct
8 Correct 520 ms 8292 KB Output is correct
9 Correct 882 ms 8340 KB Output is correct
10 Correct 440 ms 8300 KB Output is correct

Subtask #2
5.0 / 5.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 4320 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 24 ms 6672 KB Output is correct
6 Correct 81 ms 7224 KB Output is correct
7 Correct 233 ms 8256 KB Output is correct
8 Correct 520 ms 8292 KB Output is correct
9 Correct 882 ms 8340 KB Output is correct
10 Correct 440 ms 8300 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 111 ms 7388 KB Output is correct
13 Correct 113 ms 7492 KB Output is correct
14 Correct 94 ms 7380 KB Output is correct
15 Correct 431 ms 8292 KB Output is correct
16 Correct 488 ms 8352 KB Output is correct
17 Correct 455 ms 8220 KB Output is correct
18 Correct 891 ms 8380 KB Output is correct
19 Correct 879 ms 8296 KB Output is correct
20 Correct 938 ms 8424 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 3 ms 4308 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 4 ms 4300 KB Output is correct
7 Correct 4 ms 4228 KB Output is correct
8 Correct 4 ms 4308 KB Output is correct
9 Incorrect 4 ms 4308 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 3 ms 4308 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 4 ms 4300 KB Output is correct
7 Correct 4 ms 4228 KB Output is correct
8 Correct 4 ms 4308 KB Output is correct
9 Incorrect 4 ms 4308 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 3 ms 4308 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 3 ms 4308 KB Output is correct
6 Correct 4 ms 4300 KB Output is correct
7 Correct 4 ms 4228 KB Output is correct
8 Correct 4 ms 4308 KB Output is correct
9 Incorrect 4 ms 4308 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.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 4320 KB Output is correct
4 Correct 4 ms 4308 KB Output is correct
5 Correct 24 ms 6672 KB Output is correct
6 Correct 81 ms 7224 KB Output is correct
7 Correct 233 ms 8256 KB Output is correct
8 Correct 520 ms 8292 KB Output is correct
9 Correct 882 ms 8340 KB Output is correct
10 Correct 440 ms 8300 KB Output is correct
11 Correct 3 ms 4308 KB Output is correct
12 Correct 111 ms 7388 KB Output is correct
13 Correct 113 ms 7492 KB Output is correct
14 Correct 94 ms 7380 KB Output is correct
15 Correct 431 ms 8292 KB Output is correct
16 Correct 488 ms 8352 KB Output is correct
17 Correct 455 ms 8220 KB Output is correct
18 Correct 891 ms 8380 KB Output is correct
19 Correct 879 ms 8296 KB Output is correct
20 Correct 938 ms 8424 KB Output is correct
21 Correct 4 ms 4308 KB Output is correct
22 Correct 4 ms 4308 KB Output is correct
23 Correct 3 ms 4308 KB Output is correct
24 Correct 4 ms 4308 KB Output is correct
25 Correct 3 ms 4308 KB Output is correct
26 Correct 4 ms 4300 KB Output is correct
27 Correct 4 ms 4228 KB Output is correct
28 Correct 4 ms 4308 KB Output is correct
29 Incorrect 4 ms 4308 KB Output isn't correct
30 Halted 0 ms 0 KB -