oj.uz

Submission #643490

# Submission time Handle Problem Language Result Execution time Memory
643490 2022-09-22T07:09:47 Z lunchbox1 Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 254 ms 1324 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 = 1e15;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  static array<int, 2> p[N];
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    if (b == -1)
      b = 1e9;
    p[i] = {b, a};
  }
  sort(p, p + n);
  static int g[N][N];
  for (int i = 0; i < n; i++) {
    vector<int> 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 = INF;
  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] + (double) p[i][1] / (t + 1), j == 0 ? INF : f[j - 1] + (double) p[i][0] / j);
      if (k - i - 1 >= 0)
        ans = min(ans, f[t] + (double) 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 332 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 18 ms 1224 KB Output is correct
7 Correct 63 ms 1276 KB Output is correct
8 Correct 135 ms 1236 KB Output is correct
9 Correct 247 ms 1304 KB Output is correct
10 Correct 120 ms 1304 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 18 ms 1224 KB Output is correct
7 Correct 63 ms 1276 KB Output is correct
8 Correct 135 ms 1236 KB Output is correct
9 Correct 247 ms 1304 KB Output is correct
10 Correct 120 ms 1304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 24 ms 1236 KB Output is correct
13 Correct 25 ms 1324 KB Output is correct
14 Correct 25 ms 1228 KB Output is correct
15 Correct 131 ms 1308 KB Output is correct
16 Correct 123 ms 1236 KB Output is correct
17 Correct 120 ms 1308 KB Output is correct
18 Correct 250 ms 1236 KB Output is correct
19 Correct 245 ms 1304 KB Output is correct
20 Correct 242 ms 1304 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 246 ms 1316 KB Output is correct
2 Correct 254 ms 1236 KB Output is correct
3 Correct 247 ms 1308 KB Output is correct
4 Correct 246 ms 1312 KB Output is correct
5 Correct 242 ms 1236 KB Output is correct
6 Correct 244 ms 1308 KB Output is correct
7 Correct 250 ms 1236 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 18 ms 1224 KB Output is correct
7 Correct 63 ms 1276 KB Output is correct
8 Correct 135 ms 1236 KB Output is correct
9 Correct 247 ms 1304 KB Output is correct
10 Correct 120 ms 1304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 24 ms 1236 KB Output is correct
13 Correct 25 ms 1324 KB Output is correct
14 Correct 25 ms 1228 KB Output is correct
15 Correct 131 ms 1308 KB Output is correct
16 Correct 123 ms 1236 KB Output is correct
17 Correct 120 ms 1308 KB Output is correct
18 Correct 250 ms 1236 KB Output is correct
19 Correct 245 ms 1304 KB Output is correct
20 Correct 242 ms 1304 KB Output is correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -