oj.uz

Submission #884962

# Submission time Handle Problem Language Result Execution time Memory
884962 2023-12-08T18:12:55 Z EJIC_B_KEDAX Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 778 ms 994844 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) {
    return a.y < b.y;
}



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;
        }
    }
    sort(all(a), cmp);
    vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(k + 1, vector<double>(n + 1, 2e18)));
    dp[0][0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int l = 0; l <= 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 / (double)(l + 1));
                    if (l > 0) {
                        dp[i + 1][j][l] = min(dp[i + 1][j][l], dp[i][j - 1][l - 1] + a[i].y / (double)l);
                    }
                }
            }
        }
    }
    double ans = 2e18;
    for (int i = 0; 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 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 78 ms 101432 KB Output is correct
6 Correct 211 ms 250500 KB Output is correct
7 Correct 406 ms 498332 KB Output is correct
8 Correct 691 ms 746604 KB Output is correct
9 Correct 778 ms 994568 KB Output is correct
10 Correct 528 ms 696992 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 78 ms 101432 KB Output is correct
6 Correct 211 ms 250500 KB Output is correct
7 Correct 406 ms 498332 KB Output is correct
8 Correct 691 ms 746604 KB Output is correct
9 Correct 778 ms 994568 KB Output is correct
10 Correct 528 ms 696992 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 233 ms 299956 KB Output is correct
13 Correct 235 ms 300160 KB Output is correct
14 Correct 233 ms 300112 KB Output is correct
15 Correct 527 ms 696972 KB Output is correct
16 Correct 530 ms 696868 KB Output is correct
17 Correct 542 ms 696824 KB Output is correct
18 Correct 746 ms 994844 KB Output is correct
19 Correct 741 ms 994640 KB Output is correct
20 Correct 746 ms 994656 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 756 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 756 KB Output is correct
8 Correct 1 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 756 KB Output is correct
8 Correct 1 ms 348 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 748 ms 994652 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 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 78 ms 101432 KB Output is correct
6 Correct 211 ms 250500 KB Output is correct
7 Correct 406 ms 498332 KB Output is correct
8 Correct 691 ms 746604 KB Output is correct
9 Correct 778 ms 994568 KB Output is correct
10 Correct 528 ms 696992 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 233 ms 299956 KB Output is correct
13 Correct 235 ms 300160 KB Output is correct
14 Correct 233 ms 300112 KB Output is correct
15 Correct 527 ms 696972 KB Output is correct
16 Correct 530 ms 696868 KB Output is correct
17 Correct 542 ms 696824 KB Output is correct
18 Correct 746 ms 994844 KB Output is correct
19 Correct 741 ms 994640 KB Output is correct
20 Correct 746 ms 994656 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 756 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Halted 0 ms 0 KB -