oj.uz

Submission #625292

# Submission time Handle Problem Language Result Execution time Memory
625292 2022-08-09T22:57:51 Z dooompy Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 2162 ms 4492 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -