oj.uz

Submission #936312

# Submission time Handle Problem Language Result Execution time Memory
936312 2024-03-01T14:49:06 Z qwe1rt1yuiop1 Let's Win the Election (JOI22_ho_t3) C++14
10 / 100
 879 ms 998832 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
using pii = pair<int, int>;

void solve()
{
    int n, kk;
    cin >> n >> kk;
    vector<pii> v(n);
    for (auto &[b, a] : v)
    {
        cin >> a >> b;
        if (b == -1)
            b = INT_MAX;
    }
    sort(v.begin(), v.end());
    for (auto &[b, a] : v)
        if (b == INT_MAX)
            b = -1;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i)
        a[i] = v[i].second, b[i] = v[i].first;

    cout << fixed << setprecision(10);

    vector<vector<vector<double>>> dp(n + 1, vector<vector<double>>(n + 1, vector<double>(n + 2, 1e15)));
    dp[0][0][1] = 0;
    for (int i = 0; i < n; ++i)
    {
        dp[i + 1] = dp[i];
        for (int j = 0; j < n; ++j)
            for (int k = 1; k < n + 2; ++k)
            {
                dp[i + 1][j + 1][k] = min(dp[i + 1][j + 1][k], dp[i][j][k] + 1.0 * a[i] / k);
                if (b[i] != -1 && k != n + 1)
                    dp[i + 1][j + 1][k + 1] = min(dp[i + 1][j + 1][k + 1], dp[i][j][k] + 1.0 * b[i] / k);
            }
    }
    double ans = 1e15;
    for (int i = 0; i <= n; ++i)
        for (int j = kk; j <= kk; ++j)
            for (int k = 0; k < n + 2; ++k)
                ans = min(ans, dp[i][j][k]);
    assert(ans < 1e14);
    cout << ans << '\n';
    // for (auto i : dp[n])
    // {
    //     for (auto j : i)
    //         cout << j << ' ';
    //     cout << '\n';
    // }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:11:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |     for (auto &[b, a] : v)
      |                ^
Main.cpp:18:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto &[b, a] : v)
      |                ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 784 ms 998600 KB Output is correct
6 Correct 719 ms 998384 KB Output is correct
7 Correct 690 ms 998480 KB Output is correct
8 Correct 686 ms 998560 KB Output is correct
9 Correct 680 ms 998736 KB Output is correct
10 Correct 675 ms 998484 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 784 ms 998600 KB Output is correct
6 Correct 719 ms 998384 KB Output is correct
7 Correct 690 ms 998480 KB Output is correct
8 Correct 686 ms 998560 KB Output is correct
9 Correct 680 ms 998736 KB Output is correct
10 Correct 675 ms 998484 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 863 ms 998480 KB Output is correct
13 Correct 783 ms 998600 KB Output is correct
14 Correct 716 ms 998736 KB Output is correct
15 Correct 879 ms 998600 KB Output is correct
16 Correct 812 ms 998480 KB Output is correct
17 Correct 713 ms 998596 KB Output is correct
18 Correct 876 ms 998804 KB Output is correct
19 Correct 787 ms 998596 KB Output is correct
20 Correct 706 ms 998600 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 348 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

# Verdict Execution time Memory Grader output
1 Incorrect 871 ms 998832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 784 ms 998600 KB Output is correct
6 Correct 719 ms 998384 KB Output is correct
7 Correct 690 ms 998480 KB Output is correct
8 Correct 686 ms 998560 KB Output is correct
9 Correct 680 ms 998736 KB Output is correct
10 Correct 675 ms 998484 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 863 ms 998480 KB Output is correct
13 Correct 783 ms 998600 KB Output is correct
14 Correct 716 ms 998736 KB Output is correct
15 Correct 879 ms 998600 KB Output is correct
16 Correct 812 ms 998480 KB Output is correct
17 Correct 713 ms 998596 KB Output is correct
18 Correct 876 ms 998804 KB Output is correct
19 Correct 787 ms 998596 KB Output is correct
20 Correct 706 ms 998600 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 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 348 KB Output is correct
29 Incorrect 0 ms 348 KB Output isn't correct
30 Halted 0 ms 0 KB -