Submission #804534

#	Time	Username	Problem	Language	Result	Execution time	Memory
804534		MilosMilutinovic	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	310 ms	4308 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ldb double

const int MAX = 505;
const ldb inf = (ldb) 1e9;

int n, m, a[MAX], b[MAX];
int order[MAX];
ldb dp[2][MAX][MAX];

bool cmp(int i, int j) {
    int vi = (b[i] == -1 ? (int) 1e9 : b[i]);
    int vj = (b[j] == -1 ? (int) 1e9 : b[j]);
    return vi < vj;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);
    }
    for (int i = 1; i <= n; i++) {
        order[i] = i;
    }
    sort(order + 1, order + 1 + n, cmp);
    for (int k = 0; k < 2; k++) {
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= n; j++) {
                dp[k][i][j] = inf;
            }
        }
    }
    dp[0][1][0] = 0;
    for (int _i = 1; _i <= n; _i++) {
        int i = order[_i];
        int f = (_i % 2), p = 1 - f;
        for (int j = 0; j <= n + 1; j++) {
            for (int k = 0; k <= n; k++) {
                dp[f][j][k] = dp[p][j][k];
            }
        }
        if (b[i] != -1) {
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k < n; k++) {
                    dp[f][j + 1][k + 1] = min(dp[f][j + 1][k + 1], dp[p][j][k] + ((ldb) (b[i] + 0.000) / (ldb) (j + 0.000)));
                }
            }
        }
        for (int j = 1; j <= n + 1; j++) {
            for (int k = 0; k < n; k++) {
                dp[f][j][k + 1] = min(dp[f][j][k + 1], dp[p][j][k] + ((ldb) (a[i] + 0.000) / (ldb) (j + 0.000)));
            }
        }
        for (int j = 0; j <= n + 1; j++) {
            for (int k = 0; k <= n; k++) {
                dp[p][j][k] = dp[f][j][k];
            }
        }
    }
    double ans = inf;
    for (int k = 0; k < 2; k++) {
        for (int i = 1; i <= n + 1; i++) {
            ans = min(ans, dp[k][i][m]);
        }
    }
    printf("%.5lf\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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