oj.uz

Submission #884996

# Submission time Handle Problem Language Result Execution time Memory
884996 2023-12-08T19:10:10 Z EJIC_B_KEDAX Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 820 ms 994764 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 2 * a.y - a.x < 2 * b.y - 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;
        }
    }
    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 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 82 ms 101672 KB Output is correct
6 Correct 215 ms 250504 KB Output is correct
7 Correct 391 ms 498544 KB Output is correct
8 Correct 612 ms 746600 KB Output is correct
9 Correct 815 ms 994764 KB Output is correct
10 Correct 552 ms 697228 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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 82 ms 101672 KB Output is correct
6 Correct 215 ms 250504 KB Output is correct
7 Correct 391 ms 498544 KB Output is correct
8 Correct 612 ms 746600 KB Output is correct
9 Correct 815 ms 994764 KB Output is correct
10 Correct 552 ms 697228 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 243 ms 299860 KB Output is correct
13 Correct 238 ms 299864 KB Output is correct
14 Correct 242 ms 300060 KB Output is correct
15 Correct 554 ms 696804 KB Output is correct
16 Correct 544 ms 696912 KB Output is correct
17 Correct 547 ms 696992 KB Output is correct
18 Correct 773 ms 994652 KB Output is correct
19 Correct 820 ms 994652 KB Output is correct
20 Correct 765 ms 994652 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 344 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 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 344 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 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 344 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 788 ms 994700 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 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 82 ms 101672 KB Output is correct
6 Correct 215 ms 250504 KB Output is correct
7 Correct 391 ms 498544 KB Output is correct
8 Correct 612 ms 746600 KB Output is correct
9 Correct 815 ms 994764 KB Output is correct
10 Correct 552 ms 697228 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 243 ms 299860 KB Output is correct
13 Correct 238 ms 299864 KB Output is correct
14 Correct 242 ms 300060 KB Output is correct
15 Correct 554 ms 696804 KB Output is correct
16 Correct 544 ms 696912 KB Output is correct
17 Correct 547 ms 696992 KB Output is correct
18 Correct 773 ms 994652 KB Output is correct
19 Correct 820 ms 994652 KB Output is correct
20 Correct 765 ms 994652 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 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 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Incorrect 0 ms 348 KB Output isn't correct
31 Halted 0 ms 0 KB -