oj.uz

Submission #885780

# Submission time Handle Problem Language Result Execution time Memory
885780 2023-12-10T17:12:13 Z EJIC_B_KEDAX Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 845 ms 994860 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() {}

int lay = 1;

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;
}


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;
    vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(k + 1, vector<double>(n + 1, 2e18)));
    // for (int ll = 0; ll <= n; ll++) {
        sort(all(a), cmp);
        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] = 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);
                        }
                    }
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            ans = min(ans, dp[n][k][i]);
        }
        lay++;
    // }
    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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 93 ms 101668 KB Output is correct
6 Correct 274 ms 250504 KB Output is correct
7 Correct 508 ms 498516 KB Output is correct
8 Correct 669 ms 746572 KB Output is correct
9 Correct 845 ms 994792 KB Output is correct
10 Correct 585 ms 697244 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 93 ms 101668 KB Output is correct
6 Correct 274 ms 250504 KB Output is correct
7 Correct 508 ms 498516 KB Output is correct
8 Correct 669 ms 746572 KB Output is correct
9 Correct 845 ms 994792 KB Output is correct
10 Correct 585 ms 697244 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 260 ms 299972 KB Output is correct
13 Correct 259 ms 300112 KB Output is correct
14 Correct 259 ms 299900 KB Output is correct
15 Correct 585 ms 697216 KB Output is correct
16 Correct 603 ms 697240 KB Output is correct
17 Correct 579 ms 696992 KB Output is correct
18 Correct 825 ms 994456 KB Output is correct
19 Correct 827 ms 994648 KB Output is correct
20 Correct 822 ms 994780 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 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 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 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 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 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 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 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 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 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 837 ms 994860 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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 93 ms 101668 KB Output is correct
6 Correct 274 ms 250504 KB Output is correct
7 Correct 508 ms 498516 KB Output is correct
8 Correct 669 ms 746572 KB Output is correct
9 Correct 845 ms 994792 KB Output is correct
10 Correct 585 ms 697244 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 260 ms 299972 KB Output is correct
13 Correct 259 ms 300112 KB Output is correct
14 Correct 259 ms 299900 KB Output is correct
15 Correct 585 ms 697216 KB Output is correct
16 Correct 603 ms 697240 KB Output is correct
17 Correct 579 ms 696992 KB Output is correct
18 Correct 825 ms 994456 KB Output is correct
19 Correct 827 ms 994648 KB Output is correct
20 Correct 822 ms 994780 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Halted 0 ms 0 KB -