답안 #625292

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625292	2022-08-09T22:57:51 Z	dooompy	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	2162 ms	4492 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	4308 KB	Output is correct
3	Correct	4 ms	4308 KB	Output is correct
4	Correct	3 ms	4308 KB	Output is correct
5	Correct	3 ms	4308 KB	Output is correct
6	Correct	3 ms	4308 KB	Output is correct
7	Correct	4 ms	4296 KB	Output is correct
8	Correct	2 ms	4308 KB	Output is correct
9	Correct	2 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	4308 KB	Output is correct
3	Correct	4 ms	4308 KB	Output is correct
4	Correct	3 ms	4308 KB	Output is correct
5	Correct	3 ms	4308 KB	Output is correct
6	Correct	3 ms	4308 KB	Output is correct
7	Correct	4 ms	4296 KB	Output is correct
8	Correct	2 ms	4308 KB	Output is correct
9	Correct	2 ms	4308 KB	Output is correct
10	Correct	2 ms	4308 KB	Output is correct
11	Correct	2 ms	4308 KB	Output is correct
12	Correct	232 ms	4344 KB	Output is correct
13	Correct	394 ms	4464 KB	Output is correct
14	Correct	308 ms	4324 KB	Output is correct
15	Correct	1022 ms	4492 KB	Output is correct
16	Correct	1259 ms	4492 KB	Output is correct
17	Correct	490 ms	4360 KB	Output is correct
18	Correct	1550 ms	4376 KB	Output is correct
19	Correct	1372 ms	4376 KB	Output is correct
20	Correct	519 ms	4372 KB	Output is correct

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4308 KB	Output is correct
2	Correct	3 ms	4296 KB	Output is correct
3	Correct	3 ms	4308 KB	Output is correct
4	Correct	4 ms	4308 KB	Output is correct
5	Correct	4 ms	4308 KB	Output is correct
6	Correct	5 ms	4312 KB	Output is correct
7	Correct	5 ms	4308 KB	Output is correct
8	Correct	5 ms	4240 KB	Output is correct
9	Correct	4 ms	4308 KB	Output is correct
10	Correct	4 ms	4220 KB	Output is correct
11	Correct	4 ms	4308 KB	Output is correct
12	Correct	5 ms	4308 KB	Output is correct
13	Correct	5 ms	4308 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	3 ms	4308 KB	Output is correct
2	Correct	3 ms	4296 KB	Output is correct
3	Correct	3 ms	4308 KB	Output is correct
4	Correct	4 ms	4308 KB	Output is correct
5	Correct	4 ms	4308 KB	Output is correct
6	Correct	5 ms	4312 KB	Output is correct
7	Correct	5 ms	4308 KB	Output is correct
8	Correct	5 ms	4240 KB	Output is correct
9	Correct	4 ms	4308 KB	Output is correct
10	Correct	4 ms	4220 KB	Output is correct
11	Correct	4 ms	4308 KB	Output is correct
12	Correct	5 ms	4308 KB	Output is correct
13	Correct	5 ms	4308 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	3 ms	4308 KB	Output is correct
2	Correct	3 ms	4296 KB	Output is correct
3	Correct	3 ms	4308 KB	Output is correct
4	Correct	4 ms	4308 KB	Output is correct
5	Correct	4 ms	4308 KB	Output is correct
6	Correct	5 ms	4312 KB	Output is correct
7	Correct	5 ms	4308 KB	Output is correct
8	Correct	5 ms	4240 KB	Output is correct
9	Correct	4 ms	4308 KB	Output is correct
10	Correct	4 ms	4220 KB	Output is correct
11	Correct	4 ms	4308 KB	Output is correct
12	Correct	5 ms	4308 KB	Output is correct
13	Correct	5 ms	4308 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	2162 ms	4376 KB	Output is correct
2	Correct	2037 ms	4376 KB	Output is correct
3	Correct	2027 ms	4376 KB	Output is correct
4	Incorrect	2063 ms	4376 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	4308 KB	Output is correct
3	Correct	4 ms	4308 KB	Output is correct
4	Correct	3 ms	4308 KB	Output is correct
5	Correct	3 ms	4308 KB	Output is correct
6	Correct	3 ms	4308 KB	Output is correct
7	Correct	4 ms	4296 KB	Output is correct
8	Correct	2 ms	4308 KB	Output is correct
9	Correct	2 ms	4308 KB	Output is correct
10	Correct	2 ms	4308 KB	Output is correct
11	Correct	2 ms	4308 KB	Output is correct
12	Correct	232 ms	4344 KB	Output is correct
13	Correct	394 ms	4464 KB	Output is correct
14	Correct	308 ms	4324 KB	Output is correct
15	Correct	1022 ms	4492 KB	Output is correct
16	Correct	1259 ms	4492 KB	Output is correct
17	Correct	490 ms	4360 KB	Output is correct
18	Correct	1550 ms	4376 KB	Output is correct
19	Correct	1372 ms	4376 KB	Output is correct
20	Correct	519 ms	4372 KB	Output is correct
21	Correct	3 ms	4308 KB	Output is correct
22	Correct	3 ms	4296 KB	Output is correct
23	Correct	3 ms	4308 KB	Output is correct
24	Correct	4 ms	4308 KB	Output is correct
25	Correct	4 ms	4308 KB	Output is correct
26	Correct	5 ms	4312 KB	Output is correct
27	Correct	5 ms	4308 KB	Output is correct
28	Correct	5 ms	4240 KB	Output is correct
29	Correct	4 ms	4308 KB	Output is correct
30	Correct	4 ms	4220 KB	Output is correct
31	Correct	4 ms	4308 KB	Output is correct
32	Correct	5 ms	4308 KB	Output is correct
33	Correct	5 ms	4308 KB	Output is correct
34	Incorrect	5 ms	4308 KB	Output isn't correct
35	Halted	0 ms	0 KB	-

답안 #625292

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