oj.uz

Submission #750767

# Submission time Handle Problem Language Result Execution time Memory
750767 2023-05-30T09:15:47 Z Kihihihi Let's Win the Election (JOI22_ho_t3) C++17
5 / 100
 2500 ms 8500 KB 
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

short skip_cin = 0;
const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 19;
const long double EPS = 1e-9, PI = acos(-1);

void solve()
{
    long long n, k;
    vector<pair<long double, long double>> v;
    cin >> n >> k;
    v.resize(n);
    for (long long i = 0; i < n; i++)
    {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(),
        [](pair<long double, long double>& x, pair<long double, long double>& y)
        {
            if (x.second == y.second)
            {
                return x.first < y.first;
            }

            if (x.second == -1)
            {
                return false;
            }
            if (y.second == -1)
            {
                return true;
            }
            return x.second < y.second;
        }
    );

    vector<vector<long double>> dp(k + 1, vector<long double>(k + 1, INF));
    dp[0][0] = 0;
    for (long long i = 0; i < n; i++)
    {
        vector<vector<long double>> upd(k + 1, vector<long double>(k + 1, INF));
        for (long long fr = 0; fr < k + 1; fr++)
        {
            for (long long hv = 1; hv < k + 1; hv++)
            {
                upd[fr][hv] = dp[fr][hv - 1] + v[i].first / (long double)(fr + 1);
                if (fr > 0 && v[i].second != -1)
                {
                    upd[fr][hv] = min(upd[fr][hv], dp[fr - 1][hv - 1] + v[i].second / (long double)fr);
                }
                upd[fr][hv] = min(upd[fr][hv], dp[fr][hv]);
            }
        }
        swap(dp, upd);
    }

    long double ans = INF;
    for (long long i = 0; i < k + 1; i++)
    {
        ans = min(ans, dp[i][k]);
    }
    cout << fixed << setprecision(20) << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 16 ms 436 KB Output is correct
6 Correct 96 ms 860 KB Output is correct
7 Correct 425 ms 2616 KB Output is correct
8 Correct 1008 ms 4824 KB Output is correct
9 Correct 1908 ms 8500 KB Output is correct
10 Correct 813 ms 4372 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 16 ms 436 KB Output is correct
6 Correct 96 ms 860 KB Output is correct
7 Correct 425 ms 2616 KB Output is correct
8 Correct 1008 ms 4824 KB Output is correct
9 Correct 1908 ms 8500 KB Output is correct
10 Correct 813 ms 4372 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 200 ms 1072 KB Output is correct
13 Correct 177 ms 1220 KB Output is correct
14 Correct 163 ms 1336 KB Output is correct
15 Correct 1157 ms 4396 KB Output is correct
16 Correct 979 ms 4344 KB Output is correct
17 Correct 904 ms 4260 KB Output is correct
18 Execution timed out 2563 ms 8436 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 16 ms 436 KB Output is correct
6 Correct 96 ms 860 KB Output is correct
7 Correct 425 ms 2616 KB Output is correct
8 Correct 1008 ms 4824 KB Output is correct
9 Correct 1908 ms 8500 KB Output is correct
10 Correct 813 ms 4372 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 200 ms 1072 KB Output is correct
13 Correct 177 ms 1220 KB Output is correct
14 Correct 163 ms 1336 KB Output is correct
15 Correct 1157 ms 4396 KB Output is correct
16 Correct 979 ms 4344 KB Output is correct
17 Correct 904 ms 4260 KB Output is correct
18 Execution timed out 2563 ms 8436 KB Time limit exceeded
19 Halted 0 ms 0 KB -