Submission #1302077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302077		daotuankhoi	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	1101 ms	8372 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }

#define ld long double

const int MAXN = 505;
ld dp[2][MAXN][MAXN];
pair<int, int> a[MAXN];
int n, k;

int main() {
    #define NAME "test"
    if (fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a + 1, a + n + 1, [&](pair<int, int> x, pair<int, int> y) {
        int l = x.se, r = y.se;
        if (l == -1) l = 1e9;
        if (r == -1) r = 1e9;
        return pair<int, int>{l, x.fi} < pair<int, int>{r, y.fi};
    });
    for (int i = 0; i < 2; i++) for (int j = 0; j <= k; j++) for (int h = 0; h <= n + 1; h++) {
        dp[i][j][h] = 1e9;
    }
    dp[0][0][1] = 0;
    int cur = 1, prv = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int h = 1; h <= n + 1; h++) {
                dp[cur][j][h] = dp[prv][j][h]; /// skip
                if (j > 0) ckmin(dp[cur][j][h], dp[prv][j - 1][h] + (ld)a[i].fi / h);
                if (j > 0 && h > 1 && a[i].se != -1) ckmin(dp[cur][j][h], dp[prv][j - 1][h - 1] + (ld)a[i].se / (h - 1));
//                debug(dp[cur][j][h], i, j, h);
            }
        }
        prv ^= 1;
        cur ^= 1;
    }
    ld ans = 1e9;
    for (int j = 0; j <= n + 1; j++) {
        ckmin(ans, dp[prv][k][j]);
    }
    cout << fixed << setprecision(16) << ans << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23