oj.uz

답안 #922068

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922068 2024-02-05T01:27:14 Z cthbst Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 1609 ms 2452 KB 
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

const int maxn = 505;
const int INF = 1e9;

int n, k;
double a[maxn];
double b[maxn];
pair<double, double> p[maxn];
double dp[maxn][maxn];

double f(int s, int cnt) {
    vector<double> v;
    for (int i = s; i < n; i++) {
        v.push_back(a[i]);
    }
    if ((int)v.size() < cnt) return INF;
    sort(v.begin(), v.end());
    double rtn = 0;
    for (int i = 0; i < cnt; i++) {
        rtn += v[i];
    }
    return rtn;
}

double myDP(int x) {
    dp[0][0] = a[0] / (x + 1);
    dp[0][1] = b[0] / 1;
    for (int j = 2; j <= x; j++) dp[0][j] = INF;

    for (int i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + a[i] / (x + 1);
        for (int j = 1; j <= x; j++) {
            if (j > i + 1) {
                dp[i][j] = INF;
            } else {
                double A = dp[i - 1][j] + a[i] / (x + 1);
                double B = dp[i - 1][j - 1] + b[i] / j;
                dp[i][j] = min(A, B);
            }
        }
    }

    double rtn = INF;
    for (int i = 0; i < n; i++) {
        rtn = min(rtn, dp[i][x] + f(i + 1, k - x) / (x + 1));
    }
    // cout << "solve(" << x << ") = " << rtn << '\n';
    return rtn;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        if (b[i] == -1) b[i] = INF;
        p[i] = {b[i], a[i]};
    }
    sort(p, p + n);
    for (int i = 0; i < n; i++) {
        b[i] = p[i].first;
        a[i] = p[i].second;
    }
    double an = f(0, k);
    for (int x = 0; x <= k; x++) {
        an = min(an, myDP(x));
    }
    cout << fixed << setprecision(15) << an << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 67 ms 2396 KB Output is correct
6 Correct 165 ms 2436 KB Output is correct
7 Correct 329 ms 2396 KB Output is correct
8 Correct 474 ms 2448 KB Output is correct
9 Correct 561 ms 2396 KB Output is correct
10 Correct 334 ms 2440 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 67 ms 2396 KB Output is correct
6 Correct 165 ms 2436 KB Output is correct
7 Correct 329 ms 2396 KB Output is correct
8 Correct 474 ms 2448 KB Output is correct
9 Correct 561 ms 2396 KB Output is correct
10 Correct 334 ms 2440 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 205 ms 2396 KB Output is correct
13 Correct 362 ms 2392 KB Output is correct
14 Correct 291 ms 2436 KB Output is correct
15 Correct 445 ms 2440 KB Output is correct
16 Correct 804 ms 2452 KB Output is correct
17 Correct 774 ms 2436 KB Output is correct
18 Correct 561 ms 2436 KB Output is correct
19 Correct 1006 ms 2444 KB Output is correct
20 Correct 808 ms 2440 KB Output is correct

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 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 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 464 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

# 결과 실행 시간 메모리 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 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 464 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

# 결과 실행 시간 메모리 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 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 464 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1609 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 67 ms 2396 KB Output is correct
6 Correct 165 ms 2436 KB Output is correct
7 Correct 329 ms 2396 KB Output is correct
8 Correct 474 ms 2448 KB Output is correct
9 Correct 561 ms 2396 KB Output is correct
10 Correct 334 ms 2440 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 205 ms 2396 KB Output is correct
13 Correct 362 ms 2392 KB Output is correct
14 Correct 291 ms 2436 KB Output is correct
15 Correct 445 ms 2440 KB Output is correct
16 Correct 804 ms 2452 KB Output is correct
17 Correct 774 ms 2436 KB Output is correct
18 Correct 561 ms 2436 KB Output is correct
19 Correct 1006 ms 2444 KB Output is correct
20 Correct 808 ms 2440 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 0 ms 348 KB Output is correct
25 Correct 0 ms 464 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 464 KB Output is correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Halted 0 ms 0 KB -