oj.uz

Submission #800539

# Submission time Handle Problem Language Result Execution time Memory
800539 2023-08-01T15:58:55 Z caganyanmaz Let's Win the Election (JOI22_ho_t3) C++17
10 / 100
 343 ms 814852 KB 
#include <bits/stdc++.h>
//#define double  long double
#define mp(x...) array<int, 2>({x})
using namespace std;

constexpr static int INF = 1e8;
constexpr static int MXSIZE = 1000;
bitset<MXSIZE> added;
array<int, 2> a[MXSIZE];
array<int, 3> b[MXSIZE];
int n, k;

double calculate(int cc)
{
        int count = 0;
        double cost = 0;
        for (int i = 0; i < cc; i++)
        {
                cost += static_cast<double>(b[i][0]) / (i+1);
                count++;
        }
        for (int i = 0; i < n && count < k; i++)
        {
                if (added[a[i][1]])
                        continue;
                cost += static_cast<double>(a[i][0]) / (cc+1);
                count++;
        }
        assert(count == k);
        return cost;
}


constexpr static int MXSIZE2 = 101;
double dp[MXSIZE2][MXSIZE2][MXSIZE2][MXSIZE2]; // Position, expected value, filled count, current value
array<int, 2> v[MXSIZE2];
void subtask2()
{
        cin >> k;
        for (int i = 0; i < n; i++)
        {
                int aa, bb;
                cin >> aa >> bb;
                bb = (bb == -1) ? INF : bb;
                v[i] = mp(bb, aa);
        }
        for (int i = 0; i < MXSIZE2; i++)
                for (int j = 0; j < MXSIZE2; j++)
                        for (int l = 0; l < MXSIZE2; l++)
                                for (int w = 0; w < MXSIZE2; w++)
                                        if (w != 0 || l != 0)
                                                dp[i][j][l][w] = INF;
        sort(v, v + n);
        for (int i = n-1; i >= 0; i--)
        {
                double bb = v[i][0], aa = v[i][1];
                for (int j = 0; j <= k; j++)
                {
                        for (int l = 0; l <= k; l++)
                        {
                                for (int w = 0; w <= j; w++)
                                {
                                        dp[i][j][l][w] = dp[i+1][j][l][w];
                                        if (l != 0)
                                                dp[i][j][l][w] = min({dp[i][j][l][w], (w > 0) ? (dp[i+1][j][l-1][w-1] + (bb / (j-w+1))) : INF, dp[i+1][j][l-1][w] + (aa / (j - w+1))} );
                                }
                        }
                }
        }
        double best = INF;
        for (int i = 0; i <= n; i++)
                best = min(best, dp[0][i][k][i]);

        cout << fixed;
        cout << setprecision(20);
        cout << best << "\n";


}

int main()
{
        cin >> n;
        if (n < 100)
        {
                subtask2();
                return 0;
        }
        cin >> k;
        for (int i = 0; i < n; i++)
        {
                int aa, bb;
                cin >> aa >> bb;
                a[i] = mp(aa, i);
                bb = bb == -1 ? INF : bb;
                b[i] = array<int, 3>({bb, -aa, i});
        }
        sort(a, a + n);
        sort(b, b + n);
        double best = INF;
        for (int i = 0; i <= k && (i == 0 || b[i-1][0] != INF); i++)
        {
                if (i > 0)
                        added[b[i-1][2]] = true;
                best = min(best, calculate(i));
        }
        cout << fixed;
        cout << setprecision(20);
        cout << best << "\n";

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 814836 KB Output is correct
2 Correct 313 ms 814848 KB Output is correct
3 Correct 318 ms 814796 KB Output is correct
4 Correct 343 ms 814784 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 814836 KB Output is correct
2 Correct 313 ms 814848 KB Output is correct
3 Correct 318 ms 814796 KB Output is correct
4 Correct 343 ms 814784 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 316 ms 814748 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 814852 KB Output is correct
2 Correct 315 ms 814836 KB Output is correct
3 Correct 324 ms 814784 KB Output is correct
4 Correct 310 ms 814740 KB Output is correct
5 Correct 318 ms 814776 KB Output is correct
6 Correct 312 ms 814840 KB Output is correct
7 Correct 315 ms 814796 KB Output is correct
8 Correct 313 ms 814752 KB Output is correct
9 Incorrect 312 ms 814792 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 814852 KB Output is correct
2 Correct 315 ms 814836 KB Output is correct
3 Correct 324 ms 814784 KB Output is correct
4 Correct 310 ms 814740 KB Output is correct
5 Correct 318 ms 814776 KB Output is correct
6 Correct 312 ms 814840 KB Output is correct
7 Correct 315 ms 814796 KB Output is correct
8 Correct 313 ms 814752 KB Output is correct
9 Incorrect 312 ms 814792 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 814852 KB Output is correct
2 Correct 315 ms 814836 KB Output is correct
3 Correct 324 ms 814784 KB Output is correct
4 Correct 310 ms 814740 KB Output is correct
5 Correct 318 ms 814776 KB Output is correct
6 Correct 312 ms 814840 KB Output is correct
7 Correct 315 ms 814796 KB Output is correct
8 Correct 313 ms 814752 KB Output is correct
9 Incorrect 312 ms 814792 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 814836 KB Output is correct
2 Correct 313 ms 814848 KB Output is correct
3 Correct 318 ms 814796 KB Output is correct
4 Correct 343 ms 814784 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 316 ms 814748 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 331 ms 814852 KB Output is correct
22 Correct 315 ms 814836 KB Output is correct
23 Correct 324 ms 814784 KB Output is correct
24 Correct 310 ms 814740 KB Output is correct
25 Correct 318 ms 814776 KB Output is correct
26 Correct 312 ms 814840 KB Output is correct
27 Correct 315 ms 814796 KB Output is correct
28 Correct 313 ms 814752 KB Output is correct
29 Incorrect 312 ms 814792 KB Output isn't correct
30 Halted 0 ms 0 KB -