답안 #625173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625173	2022-08-09T14:18:27 Z	dooompy	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	2099 ms	4460 KB

Main

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

vector<pair<int, int>> v;

int goal, n, k;

long double dp[505][505];

long double solve(int node, int ctcollab) {
    if (dp[node][ctcollab] != -1) return dp[node][ctcollab];

    if (node == n) return 1e9;

    int ctnorm = node - ctcollab;

    if (ctcollab == goal) {
        vector<pair<int, int>> cur;
        for (int i = node; i < n; i++) {
            cur.emplace_back(v[i]);
        }

        sort(cur.begin(), cur.end());
        long double ct = 0;

        for (int i = 0; i < k - node; i++) {
            ct += ((long double) cur[i].first) / (ctcollab + 1);
        }

        return dp[node][ctcollab] = ct;
    }

    long double ans = solve(node + 1, ctcollab + 1) + ((long double) v[node].second) / (ctcollab + 1);

    if (ctnorm + ctcollab < k) {
        ans = min(ans, solve(node + 1, ctcollab) + ((long double) v[node].first) / (goal + 1));
    }
//    cout << ans << endl;
    return dp[node][ctcollab] = ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        if (b == -1) b = 1e9;
        v.emplace_back(a, b);
    }

    sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b) {
        return a.second < b.second;
    });

    long double ans = 1e18;

    for (int i = 0; i < k; i++) {
        if (i >= 1 && v[i-1].second == 1e9) break;
        goal = i;
        fill(&dp[0][0], &dp[0][0] + sizeof(dp) / sizeof(dp[0][0]), -1);
        long double res = solve(0, 0);

        ans = min(ans, res);
    }

    cout << fixed << setprecision(10) << ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4308 KB	Output is correct
2	Correct	2 ms	4300 KB	Output is correct
3	Correct	3 ms	4180 KB	Output is correct
4	Correct	2 ms	4308 KB	Output is correct
5	Correct	2 ms	4292 KB	Output is correct
6	Correct	2 ms	4308 KB	Output is correct
7	Correct	2 ms	4300 KB	Output is correct
8	Correct	2 ms	4308 KB	Output is correct
9	Correct	3 ms	4308 KB	Output is correct
10	Correct	2 ms	4308 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4308 KB	Output is correct
2	Correct	2 ms	4300 KB	Output is correct
3	Correct	3 ms	4180 KB	Output is correct
4	Correct	2 ms	4308 KB	Output is correct
5	Correct	2 ms	4292 KB	Output is correct
6	Correct	2 ms	4308 KB	Output is correct
7	Correct	2 ms	4300 KB	Output is correct
8	Correct	2 ms	4308 KB	Output is correct
9	Correct	3 ms	4308 KB	Output is correct
10	Correct	2 ms	4308 KB	Output is correct
11	Correct	3 ms	4308 KB	Output is correct
12	Correct	240 ms	4340 KB	Output is correct
13	Correct	396 ms	4460 KB	Output is correct
14	Correct	317 ms	4336 KB	Output is correct
15	Correct	999 ms	4372 KB	Output is correct
16	Correct	1282 ms	4376 KB	Output is correct
17	Correct	493 ms	4368 KB	Output is correct
18	Correct	1456 ms	4372 KB	Output is correct
19	Correct	1272 ms	4372 KB	Output is correct
20	Correct	494 ms	4372 KB	Output is correct

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4308 KB	Output is correct
2	Correct	3 ms	4180 KB	Output is correct
3	Correct	3 ms	4308 KB	Output is correct
4	Correct	4 ms	4180 KB	Output is correct
5	Correct	4 ms	4308 KB	Output is correct
6	Correct	5 ms	4308 KB	Output is correct
7	Correct	5 ms	4304 KB	Output is correct
8	Correct	4 ms	4308 KB	Output is correct
9	Correct	4 ms	4204 KB	Output is correct
10	Correct	4 ms	4296 KB	Output is correct
11	Correct	4 ms	4308 KB	Output is correct
12	Correct	4 ms	4292 KB	Output is correct
13	Correct	6 ms	4240 KB	Output is correct
14	Incorrect	5 ms	4308 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4308 KB	Output is correct
2	Correct	3 ms	4180 KB	Output is correct
3	Correct	3 ms	4308 KB	Output is correct
4	Correct	4 ms	4180 KB	Output is correct
5	Correct	4 ms	4308 KB	Output is correct
6	Correct	5 ms	4308 KB	Output is correct
7	Correct	5 ms	4304 KB	Output is correct
8	Correct	4 ms	4308 KB	Output is correct
9	Correct	4 ms	4204 KB	Output is correct
10	Correct	4 ms	4296 KB	Output is correct
11	Correct	4 ms	4308 KB	Output is correct
12	Correct	4 ms	4292 KB	Output is correct
13	Correct	6 ms	4240 KB	Output is correct
14	Incorrect	5 ms	4308 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5
0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4308 KB	Output is correct
2	Correct	3 ms	4180 KB	Output is correct
3	Correct	3 ms	4308 KB	Output is correct
4	Correct	4 ms	4180 KB	Output is correct
5	Correct	4 ms	4308 KB	Output is correct
6	Correct	5 ms	4308 KB	Output is correct
7	Correct	5 ms	4304 KB	Output is correct
8	Correct	4 ms	4308 KB	Output is correct
9	Correct	4 ms	4204 KB	Output is correct
10	Correct	4 ms	4296 KB	Output is correct
11	Correct	4 ms	4308 KB	Output is correct
12	Correct	4 ms	4292 KB	Output is correct
13	Correct	6 ms	4240 KB	Output is correct
14	Incorrect	5 ms	4308 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2099 ms	4372 KB	Output is correct
2	Correct	2003 ms	4372 KB	Output is correct
3	Correct	2025 ms	4368 KB	Output is correct
4	Incorrect	2049 ms	4372 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4308 KB	Output is correct
2	Correct	2 ms	4300 KB	Output is correct
3	Correct	3 ms	4180 KB	Output is correct
4	Correct	2 ms	4308 KB	Output is correct
5	Correct	2 ms	4292 KB	Output is correct
6	Correct	2 ms	4308 KB	Output is correct
7	Correct	2 ms	4300 KB	Output is correct
8	Correct	2 ms	4308 KB	Output is correct
9	Correct	3 ms	4308 KB	Output is correct
10	Correct	2 ms	4308 KB	Output is correct
11	Correct	3 ms	4308 KB	Output is correct
12	Correct	240 ms	4340 KB	Output is correct
13	Correct	396 ms	4460 KB	Output is correct
14	Correct	317 ms	4336 KB	Output is correct
15	Correct	999 ms	4372 KB	Output is correct
16	Correct	1282 ms	4376 KB	Output is correct
17	Correct	493 ms	4368 KB	Output is correct
18	Correct	1456 ms	4372 KB	Output is correct
19	Correct	1272 ms	4372 KB	Output is correct
20	Correct	494 ms	4372 KB	Output is correct
21	Correct	2 ms	4308 KB	Output is correct
22	Correct	3 ms	4180 KB	Output is correct
23	Correct	3 ms	4308 KB	Output is correct
24	Correct	4 ms	4180 KB	Output is correct
25	Correct	4 ms	4308 KB	Output is correct
26	Correct	5 ms	4308 KB	Output is correct
27	Correct	5 ms	4304 KB	Output is correct
28	Correct	4 ms	4308 KB	Output is correct
29	Correct	4 ms	4204 KB	Output is correct
30	Correct	4 ms	4296 KB	Output is correct
31	Correct	4 ms	4308 KB	Output is correct
32	Correct	4 ms	4292 KB	Output is correct
33	Correct	6 ms	4240 KB	Output is correct
34	Incorrect	5 ms	4308 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #625173

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 11.0

Subtask #4 0 / 12.0

Subtask #5 0 / 33.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 11.0

Subtask #4
0 / 12.0

Subtask #5
0 / 33.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0