oj.uz

Submission #643493

# Submission time Handle Problem Language Result Execution time Memory
643493 2022-09-22T07:15:32 Z lunchbox1 Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 213 ms 2312 KB 
/*
sort by b from small to large

optimal construction can be split into two halves
- on the left, all the things are taken
- on the right, only a's are taken

fix the number of b's, let this be t
f(i,j) = min time to use prefix i with j b's
f(i,j) = min(f(i-1,j) + a[i] / t, f(i-1,j-1) + b[i] / t)

now for the suffixes, we need to pick k-i a's at the end,
we must pick the ones with the least a[j] value. this part
can be done in O(n log^2 n)

overall the time complexity is O(n^3)
*/
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
  #include "debug.h"
#else
  #define debug(...) 0
#endif

const int N = 505;
const double INF = 1e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  static array<double, 2> p[N];
  for (int i = 0; i < n; i++) {
    double a, b;
    cin >> a >> b;
    if (b == -1)
      b = INF;
    p[i] = {b, a};
  }
  sort(p, p + n);
  static double g[N][N];
  for (int i = 0; i < n; i++) {
    vector<double> t;
    for (int j = i; j < n; j++)
      t.push_back(p[j][1]);
    sort(t.begin(), t.end());
    g[i][0] = 0;
    for (int j = 1; j <= (int) t.size(); j++)
      g[i][j] = g[i][j - 1] + t[j - 1];
  }
  double ans = g[0][n];
  for (int t = 0; t <= k; t++) {
    static double f[N];
    for (int i = 0; i <= k; i++)
      f[i] = INF;
    f[0] = 0;
    for (int i = 0; i < n; i++) {
      for (int j = k; j >= 0; j--)
        f[j] = min(f[j] + p[i][1] / (t + 1), j == 0 ? INF : f[j - 1] + p[i][0] / j);
      if (k - i - 1 >= 0)
        ans = min(ans, f[t] + g[i + 1][k - i - 1] / (t + 1));
    }
  }
  cout << fixed << setprecision(12) << ans << '\n';
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 5 ms 2260 KB Output is correct
6 Correct 16 ms 2260 KB Output is correct
7 Correct 59 ms 2260 KB Output is correct
8 Correct 119 ms 2260 KB Output is correct
9 Correct 202 ms 2292 KB Output is correct
10 Correct 95 ms 2260 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 5 ms 2260 KB Output is correct
6 Correct 16 ms 2260 KB Output is correct
7 Correct 59 ms 2260 KB Output is correct
8 Correct 119 ms 2260 KB Output is correct
9 Correct 202 ms 2292 KB Output is correct
10 Correct 95 ms 2260 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 26 ms 2312 KB Output is correct
13 Correct 29 ms 2312 KB Output is correct
14 Correct 27 ms 2312 KB Output is correct
15 Correct 105 ms 2296 KB Output is correct
16 Correct 98 ms 2260 KB Output is correct
17 Correct 102 ms 2296 KB Output is correct
18 Correct 187 ms 2296 KB Output is correct
19 Correct 189 ms 2296 KB Output is correct
20 Correct 195 ms 2312 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 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 340 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 2296 KB Output is correct
2 Correct 213 ms 2300 KB Output is correct
3 Correct 194 ms 2292 KB Output is correct
4 Correct 192 ms 2296 KB Output is correct
5 Correct 205 ms 2308 KB Output is correct
6 Correct 191 ms 2296 KB Output is correct
7 Correct 192 ms 2260 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 5 ms 2260 KB Output is correct
6 Correct 16 ms 2260 KB Output is correct
7 Correct 59 ms 2260 KB Output is correct
8 Correct 119 ms 2260 KB Output is correct
9 Correct 202 ms 2292 KB Output is correct
10 Correct 95 ms 2260 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 26 ms 2312 KB Output is correct
13 Correct 29 ms 2312 KB Output is correct
14 Correct 27 ms 2312 KB Output is correct
15 Correct 105 ms 2296 KB Output is correct
16 Correct 98 ms 2260 KB Output is correct
17 Correct 102 ms 2296 KB Output is correct
18 Correct 187 ms 2296 KB Output is correct
19 Correct 189 ms 2296 KB Output is correct
20 Correct 195 ms 2312 KB Output is correct
21 Incorrect 0 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -