oj.uz

Submission #885826

# Submission time Handle Problem Language Result Execution time Memory
885826 2023-12-10T19:48:14 Z EJIC_B_KEDAX Let's Win the Election (JOI22_ho_t3) C++17
100 / 100
 1283 ms 1039120 KB 
#ifdef LOCAL
    //#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
    //#pragma GCC optimize("O3")
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937_64 mt(418);

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    // srand(time(0));
    init();
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

void init() {}

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    if (a.y < b.y) {
        return true;
    }
    if (a.y > b.y) {
        return false;
    }
    return a.x < b.x;
}

double dp[510][510][510]{};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
        if (a[i].y == -1) {
            a[i].y = INT32_MAX / 2;
        }
    }
    double ans = 2e18;
    double dell[510];
    for (int i = 1; i < 510; i++) {
        dell[i] = 1.0 / i;
    }
    // vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(k + 1, vector<double>(n + 1, 2e18)));
    for (int i = 0; i < 510; i++) {
        for (int j = 0; j < 510; j++) {
            for (int l = 0; l < 510; l++) {
                dp[i][j][l] = 3e18;
            }
        }
    }
    for (int ll = 0; ll <= n; ll++) {
        sort(all(a), cmp);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= min(i + 1, k); j++) {
                if (i == j - 1) {
                    for (int l = 0; l <= min(i + 1, n); l++) {
                        dp[i + 1][j][l] = 3e18;
                    }
                } else {
                    dp[i + 1][j][ll] = 3e18;
                }
            }
        }
        dp[0][0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= min(i + 1, k); j++) {
                if (i == j - 1) {
                    for (int l = 0; l <= min(i + 1, n); l++) {
                        dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j][l]);
                        if (j > 0) {
                            dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j - 1][l] + a[i].x * dell[ll + 1]);
                            if (l > 0) {
                                dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j - 1][l - 1] + a[i].y * dell[l]);
                            }
                        }
                    }
                } else {
                    dp[i + 1][j][ll] = min(dp[i + 1][j][ll], dp[i][j][ll]);
                    if (j > 0) {
                        dp[i + 1][j][ll] = min(dp[i + 1][j][ll], dp[i][j - 1][ll] + a[i].x * dell[ll + 1]);
                    }
                }
            }
        }
        for (int i = ll; i <= n; i++) {
            ans = min(ans, dp[n][k][i]);
        }
    }
    cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 1038732 KB Output is correct
2 Correct 151 ms 1038940 KB Output is correct
3 Correct 145 ms 1038728 KB Output is correct
4 Correct 148 ms 1038672 KB Output is correct
5 Correct 274 ms 1038860 KB Output is correct
6 Correct 434 ms 1038780 KB Output is correct
7 Correct 709 ms 1038800 KB Output is correct
8 Correct 1010 ms 1038808 KB Output is correct
9 Correct 1185 ms 1038804 KB Output is correct
10 Correct 954 ms 1038928 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 1038732 KB Output is correct
2 Correct 151 ms 1038940 KB Output is correct
3 Correct 145 ms 1038728 KB Output is correct
4 Correct 148 ms 1038672 KB Output is correct
5 Correct 274 ms 1038860 KB Output is correct
6 Correct 434 ms 1038780 KB Output is correct
7 Correct 709 ms 1038800 KB Output is correct
8 Correct 1010 ms 1038808 KB Output is correct
9 Correct 1185 ms 1038804 KB Output is correct
10 Correct 954 ms 1038928 KB Output is correct
11 Correct 148 ms 1038564 KB Output is correct
12 Correct 479 ms 1039120 KB Output is correct
13 Correct 480 ms 1038672 KB Output is correct
14 Correct 492 ms 1038596 KB Output is correct
15 Correct 990 ms 1038996 KB Output is correct
16 Correct 966 ms 1038808 KB Output is correct
17 Correct 944 ms 1038808 KB Output is correct
18 Correct 1283 ms 1038808 KB Output is correct
19 Correct 1278 ms 1038804 KB Output is correct
20 Correct 1204 ms 1038816 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1038672 KB Output is correct
2 Correct 147 ms 1038672 KB Output is correct
3 Correct 152 ms 1038672 KB Output is correct
4 Correct 145 ms 1038696 KB Output is correct
5 Correct 151 ms 1038672 KB Output is correct
6 Correct 151 ms 1038676 KB Output is correct
7 Correct 150 ms 1038676 KB Output is correct
8 Correct 147 ms 1038728 KB Output is correct
9 Correct 147 ms 1038676 KB Output is correct
10 Correct 154 ms 1038924 KB Output is correct
11 Correct 149 ms 1038640 KB Output is correct
12 Correct 148 ms 1038588 KB Output is correct
13 Correct 152 ms 1038680 KB Output is correct
14 Correct 145 ms 1038796 KB Output is correct
15 Correct 146 ms 1038676 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1038672 KB Output is correct
2 Correct 147 ms 1038672 KB Output is correct
3 Correct 152 ms 1038672 KB Output is correct
4 Correct 145 ms 1038696 KB Output is correct
5 Correct 151 ms 1038672 KB Output is correct
6 Correct 151 ms 1038676 KB Output is correct
7 Correct 150 ms 1038676 KB Output is correct
8 Correct 147 ms 1038728 KB Output is correct
9 Correct 147 ms 1038676 KB Output is correct
10 Correct 154 ms 1038924 KB Output is correct
11 Correct 149 ms 1038640 KB Output is correct
12 Correct 148 ms 1038588 KB Output is correct
13 Correct 152 ms 1038680 KB Output is correct
14 Correct 145 ms 1038796 KB Output is correct
15 Correct 146 ms 1038676 KB Output is correct
16 Correct 149 ms 1038676 KB Output is correct
17 Correct 171 ms 1038656 KB Output is correct
18 Correct 149 ms 1038800 KB Output is correct
19 Correct 147 ms 1038672 KB Output is correct
20 Correct 157 ms 1038868 KB Output is correct
21 Correct 151 ms 1038576 KB Output is correct
22 Correct 147 ms 1038676 KB Output is correct
23 Correct 151 ms 1038676 KB Output is correct
24 Correct 149 ms 1038780 KB Output is correct
25 Correct 145 ms 1038672 KB Output is correct
26 Correct 161 ms 1038672 KB Output is correct
27 Correct 151 ms 1038924 KB Output is correct
28 Correct 146 ms 1038736 KB Output is correct
29 Correct 146 ms 1038740 KB Output is correct
30 Correct 154 ms 1038720 KB Output is correct
31 Correct 145 ms 1038716 KB Output is correct
32 Correct 147 ms 1038676 KB Output is correct
33 Correct 146 ms 1038788 KB Output is correct
34 Correct 151 ms 1038780 KB Output is correct
35 Correct 150 ms 1038676 KB Output is correct
36 Correct 146 ms 1038712 KB Output is correct
37 Correct 151 ms 1038924 KB Output is correct
38 Correct 146 ms 1038660 KB Output is correct
39 Correct 157 ms 1038668 KB Output is correct
40 Correct 149 ms 1038788 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1038672 KB Output is correct
2 Correct 147 ms 1038672 KB Output is correct
3 Correct 152 ms 1038672 KB Output is correct
4 Correct 145 ms 1038696 KB Output is correct
5 Correct 151 ms 1038672 KB Output is correct
6 Correct 151 ms 1038676 KB Output is correct
7 Correct 150 ms 1038676 KB Output is correct
8 Correct 147 ms 1038728 KB Output is correct
9 Correct 147 ms 1038676 KB Output is correct
10 Correct 154 ms 1038924 KB Output is correct
11 Correct 149 ms 1038640 KB Output is correct
12 Correct 148 ms 1038588 KB Output is correct
13 Correct 152 ms 1038680 KB Output is correct
14 Correct 145 ms 1038796 KB Output is correct
15 Correct 146 ms 1038676 KB Output is correct
16 Correct 149 ms 1038676 KB Output is correct
17 Correct 171 ms 1038656 KB Output is correct
18 Correct 149 ms 1038800 KB Output is correct
19 Correct 147 ms 1038672 KB Output is correct
20 Correct 157 ms 1038868 KB Output is correct
21 Correct 151 ms 1038576 KB Output is correct
22 Correct 147 ms 1038676 KB Output is correct
23 Correct 151 ms 1038676 KB Output is correct
24 Correct 149 ms 1038780 KB Output is correct
25 Correct 145 ms 1038672 KB Output is correct
26 Correct 161 ms 1038672 KB Output is correct
27 Correct 151 ms 1038924 KB Output is correct
28 Correct 146 ms 1038736 KB Output is correct
29 Correct 146 ms 1038740 KB Output is correct
30 Correct 154 ms 1038720 KB Output is correct
31 Correct 145 ms 1038716 KB Output is correct
32 Correct 147 ms 1038676 KB Output is correct
33 Correct 146 ms 1038788 KB Output is correct
34 Correct 151 ms 1038780 KB Output is correct
35 Correct 150 ms 1038676 KB Output is correct
36 Correct 146 ms 1038712 KB Output is correct
37 Correct 151 ms 1038924 KB Output is correct
38 Correct 146 ms 1038660 KB Output is correct
39 Correct 157 ms 1038668 KB Output is correct
40 Correct 149 ms 1038788 KB Output is correct
41 Correct 146 ms 1038676 KB Output is correct
42 Correct 147 ms 1038672 KB Output is correct
43 Correct 146 ms 1038592 KB Output is correct
44 Correct 151 ms 1038912 KB Output is correct
45 Correct 151 ms 1038660 KB Output is correct
46 Correct 148 ms 1038788 KB Output is correct
47 Correct 151 ms 1038928 KB Output is correct
48 Correct 150 ms 1038676 KB Output is correct
49 Correct 148 ms 1038672 KB Output is correct
50 Correct 152 ms 1038692 KB Output is correct
51 Correct 148 ms 1038756 KB Output is correct
52 Correct 151 ms 1038672 KB Output is correct
53 Correct 147 ms 1038624 KB Output is correct
54 Correct 153 ms 1038740 KB Output is correct
55 Correct 147 ms 1038700 KB Output is correct
56 Correct 153 ms 1038676 KB Output is correct
57 Correct 149 ms 1038596 KB Output is correct
58 Correct 153 ms 1038672 KB Output is correct
59 Correct 154 ms 1038796 KB Output is correct
60 Correct 148 ms 1038564 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1215 ms 1038792 KB Output is correct
2 Correct 1241 ms 1038804 KB Output is correct
3 Correct 1208 ms 1038932 KB Output is correct
4 Correct 1243 ms 1039056 KB Output is correct
5 Correct 1241 ms 1038804 KB Output is correct
6 Correct 1260 ms 1039028 KB Output is correct
7 Correct 1248 ms 1038812 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 1038732 KB Output is correct
2 Correct 151 ms 1038940 KB Output is correct
3 Correct 145 ms 1038728 KB Output is correct
4 Correct 148 ms 1038672 KB Output is correct
5 Correct 274 ms 1038860 KB Output is correct
6 Correct 434 ms 1038780 KB Output is correct
7 Correct 709 ms 1038800 KB Output is correct
8 Correct 1010 ms 1038808 KB Output is correct
9 Correct 1185 ms 1038804 KB Output is correct
10 Correct 954 ms 1038928 KB Output is correct
11 Correct 148 ms 1038564 KB Output is correct
12 Correct 479 ms 1039120 KB Output is correct
13 Correct 480 ms 1038672 KB Output is correct
14 Correct 492 ms 1038596 KB Output is correct
15 Correct 990 ms 1038996 KB Output is correct
16 Correct 966 ms 1038808 KB Output is correct
17 Correct 944 ms 1038808 KB Output is correct
18 Correct 1283 ms 1038808 KB Output is correct
19 Correct 1278 ms 1038804 KB Output is correct
20 Correct 1204 ms 1038816 KB Output is correct
21 Correct 147 ms 1038672 KB Output is correct
22 Correct 147 ms 1038672 KB Output is correct
23 Correct 152 ms 1038672 KB Output is correct
24 Correct 145 ms 1038696 KB Output is correct
25 Correct 151 ms 1038672 KB Output is correct
26 Correct 151 ms 1038676 KB Output is correct
27 Correct 150 ms 1038676 KB Output is correct
28 Correct 147 ms 1038728 KB Output is correct
29 Correct 147 ms 1038676 KB Output is correct
30 Correct 154 ms 1038924 KB Output is correct
31 Correct 149 ms 1038640 KB Output is correct
32 Correct 148 ms 1038588 KB Output is correct
33 Correct 152 ms 1038680 KB Output is correct
34 Correct 145 ms 1038796 KB Output is correct
35 Correct 146 ms 1038676 KB Output is correct
36 Correct 149 ms 1038676 KB Output is correct
37 Correct 171 ms 1038656 KB Output is correct
38 Correct 149 ms 1038800 KB Output is correct
39 Correct 147 ms 1038672 KB Output is correct
40 Correct 157 ms 1038868 KB Output is correct
41 Correct 151 ms 1038576 KB Output is correct
42 Correct 147 ms 1038676 KB Output is correct
43 Correct 151 ms 1038676 KB Output is correct
44 Correct 149 ms 1038780 KB Output is correct
45 Correct 145 ms 1038672 KB Output is correct
46 Correct 161 ms 1038672 KB Output is correct
47 Correct 151 ms 1038924 KB Output is correct
48 Correct 146 ms 1038736 KB Output is correct
49 Correct 146 ms 1038740 KB Output is correct
50 Correct 154 ms 1038720 KB Output is correct
51 Correct 145 ms 1038716 KB Output is correct
52 Correct 147 ms 1038676 KB Output is correct
53 Correct 146 ms 1038788 KB Output is correct
54 Correct 151 ms 1038780 KB Output is correct
55 Correct 150 ms 1038676 KB Output is correct
56 Correct 146 ms 1038712 KB Output is correct
57 Correct 151 ms 1038924 KB Output is correct
58 Correct 146 ms 1038660 KB Output is correct
59 Correct 157 ms 1038668 KB Output is correct
60 Correct 149 ms 1038788 KB Output is correct
61 Correct 146 ms 1038676 KB Output is correct
62 Correct 147 ms 1038672 KB Output is correct
63 Correct 146 ms 1038592 KB Output is correct
64 Correct 151 ms 1038912 KB Output is correct
65 Correct 151 ms 1038660 KB Output is correct
66 Correct 148 ms 1038788 KB Output is correct
67 Correct 151 ms 1038928 KB Output is correct
68 Correct 150 ms 1038676 KB Output is correct
69 Correct 148 ms 1038672 KB Output is correct
70 Correct 152 ms 1038692 KB Output is correct
71 Correct 148 ms 1038756 KB Output is correct
72 Correct 151 ms 1038672 KB Output is correct
73 Correct 147 ms 1038624 KB Output is correct
74 Correct 153 ms 1038740 KB Output is correct
75 Correct 147 ms 1038700 KB Output is correct
76 Correct 153 ms 1038676 KB Output is correct
77 Correct 149 ms 1038596 KB Output is correct
78 Correct 153 ms 1038672 KB Output is correct
79 Correct 154 ms 1038796 KB Output is correct
80 Correct 148 ms 1038564 KB Output is correct
81 Correct 1215 ms 1038792 KB Output is correct
82 Correct 1241 ms 1038804 KB Output is correct
83 Correct 1208 ms 1038932 KB Output is correct
84 Correct 1243 ms 1039056 KB Output is correct
85 Correct 1241 ms 1038804 KB Output is correct
86 Correct 1260 ms 1039028 KB Output is correct
87 Correct 1248 ms 1038812 KB Output is correct
88 Correct 273 ms 1038672 KB Output is correct
89 Correct 274 ms 1038952 KB Output is correct
90 Correct 426 ms 1038676 KB Output is correct
91 Correct 431 ms 1038804 KB Output is correct
92 Correct 719 ms 1038808 KB Output is correct
93 Correct 712 ms 1038808 KB Output is correct
94 Correct 1056 ms 1038804 KB Output is correct
95 Correct 1026 ms 1038812 KB Output is correct
96 Correct 1132 ms 1038812 KB Output is correct
97 Correct 1165 ms 1038668 KB Output is correct
98 Correct 956 ms 1038916 KB Output is correct
99 Correct 1012 ms 1038968 KB Output is correct
100 Correct 966 ms 1038996 KB Output is correct
101 Correct 1022 ms 1038804 KB Output is correct
102 Correct 966 ms 1038800 KB Output is correct
103 Correct 990 ms 1038588 KB Output is correct
104 Correct 972 ms 1038984 KB Output is correct
105 Correct 1002 ms 1038808 KB Output is correct