oj.uz

Submission #800546

# Submission time Handle Problem Language Result Execution time Memory
800546 2023-08-01T16:03:00 Z caganyanmaz Let's Win the Election (JOI22_ho_t3) C++17
0 / 100
 423 ms 1048576 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 = 120;
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+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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 423 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 423 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 387 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 387 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 387 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Runtime error 423 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -