QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#672312	#2629. Let's Win the Election	liuziao	39	19ms	5916kb	C++23	2.6kb	2024-10-24 16:26:01	2024-10-24 16:26:01

Judging History

你现在查看的是最新测评结果

[2024-10-24 16:26:01]
评测

测评结果：39
用时：19ms
内存：5916kb

查看

[2024-10-24 16:26:01]
提交

answer

#include <bits/stdc++.h>

// #define int int64_t

using f64 = double;
using pii = std::pair<int, int>;

const int kMaxN = 505;
const f64 kEps = 1e-6;

int n, k;
pii a[kMaxN];
f64 f[kMaxN][kMaxN];

f64 func(int cnt) {
  static pii b[kMaxN];
  for (int i = 1; i <= n; ++i) b[i] = a[i];
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j <= n; ++j)
      f[i][j] = 1e9;
  f[0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = cnt; ~j; --j) {
      // for (int k = ::k - cnt; ~k; --k) {
      //   if (j && a[i].second != -1) f[j][k] = std::min(f[j][k], f[j - 1][k] + (f64)a[i].second / j);
      //   if (k) f[j][k] = std::min(f[j][k], f[j][k - 1] + (f64)a[i].first / (cnt + 1));
      // }
      f[i][j] = f[i - 1][j] + (f64)a[i].first / (cnt + 1);
      if (j && a[i].second != -1) f[i][j] = std::min(f[i][j], f[i - 1][j - 1] + (f64)a[i].second / j);
    }
  }
  f64 ret = 1e9;
  for (int i = k; i >= cnt; --i) {
    std::sort(b + 1 + i, b + 1 + n);
    f64 sum = f[i][cnt];
    for (int j = i + 1; j <= k; ++j) sum += (f64)b[j].first / (cnt + 1);
    ret = std::min(ret, sum);
  }
  return ret;
}

void dickdreamer() {
  std::cin >> n >> k;
  int can = 0;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i].first >> a[i].second;
    if (a[i].second != -1) ++can;
  }
  std::sort(a + 1, a + 1 + n, [&] (pii p1, pii p2) { return p1.second < p2.second; });
  f64 ans = 1e9;
  // for (int cnt = 0; cnt <= std::min(can, k); ++cnt) {
  //   for (int i = 0; i <= n; ++i)
  //     for (int j = 0; j <= n; ++j)
  //       f[i][j] = 1e9;
  //   f[0][0] = 0;
  //   for (int i = 1; i <= n; ++i) {
  //     for (int j = cnt; ~j; --j) {
  //       for (int k = ::k - cnt; ~k; --k) {
  //         if (j && a[i].second != -1) f[j][k] = std::min(f[j][k], f[j - 1][k] + (f64)a[i].second / j);
  //         if (k) f[j][k] = std::min(f[j][k], f[j][k - 1] + (f64)a[i].first / (cnt + 1));
  //       }
  //     }
  //   }
  //   ans = std::min(ans, f[cnt][k - cnt]);
  // }
  int L = 0, R = std::min(can, k) + 1, res = 0;
  while (L + 1 < R) {
    int mid = (L + R) >> 1;
    if (func(mid) <= func(mid - 1) - kEps) L = res = mid;
    else R = mid;
  }
  std::cout << std::fixed << std::setprecision(10) << func(res) << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 3832kb

input:

1
1
729 -1

output:

729.0000000000

result:

ok error = 0.000000000

Test #2:

score: 5

Accepted

time: 0ms

memory: 3920kb

input:

output:

300.0000000000

result:

ok error = 0.000000000

Test #3:

score: 5

Accepted

time: 0ms

memory: 3848kb

input:

output:

1140.0000000000

result:

ok error = 0.000000000

Test #4:

score: 5

Accepted

time: 0ms

memory: 3840kb

input:

output:

1059.0000000000

result:

ok error = 0.000000000

Test #5:

score: 5

Accepted

time: 1ms

memory: 5776kb

input:

output:

2580.0000000000

result:

ok error = 0.000000000

Test #6:

score: 5

Accepted

time: 2ms

memory: 5896kb

input:

output:

15729.0000000000

result:

ok error = 0.000000000

Test #7:

score: 5

Accepted

time: 2ms

memory: 5872kb

input:

output:

66687.0000000000

result:

ok error = 0.000000000

Test #8:

score: 5

Accepted

time: 0ms

memory: 5804kb

input:

output:

147876.0000000000

result:

ok error = 0.000000000

Test #9:

score: 5

Accepted

time: 0ms

memory: 5808kb

input:

output:

249562.0000000000

result:

ok error = 0.000000000

Test #10:

score: 5

Accepted

time: 2ms

memory: 5676kb

input:

output:

350000.0000000000

result:

ok error = 0.000000000

Subtask #2:

score: 0

Wrong Answer

Test #11:

score: 5

Accepted

time: 0ms

memory: 3896kb

input:

1
1
791 791

output:

791.0000000000

result:

ok error = 0.000000000

Test #12:

score: 5

Accepted

time: 4ms

memory: 5868kb

input:

output:

341.0793145790

result:

ok error = 0.000000000

Test #13:

score: 0

Wrong Answer

time: 10ms

memory: 5872kb

input:

output:

21229.0000000000

result:

wrong answer read 21229.000000000 but expected 355.342286415, error = 20873.657713585

Subtask #3:

score: 0

Wrong Answer

Test #21:

score: 11

Accepted

time: 0ms

memory: 3852kb

input:

output:

51.0000000000

result:

ok error = 0.000000000

Test #22:

score: 11

Accepted

time: 0ms

memory: 3868kb

input:

output:

68.0000000000

result:

ok error = 0.000000000

Test #23:

score: 0

Wrong Answer

time: 0ms

memory: 3916kb

input:

output:

413.0000000000

result:

wrong answer read 413.000000000 but expected 301.500000000, error = 111.500000000

Subtask #4:

score: 0

Wrong Answer

Test #36:

score: 12

Accepted

time: 0ms

memory: 3920kb

input:

output:

112.0000000000

result:

ok error = 0.000000000

Test #37:

score: 12

Accepted

time: 0ms

memory: 3988kb

input:

output:

372.9166666667

result:

ok error = 0.000000000

Test #38:

score: 0

Wrong Answer

time: 0ms

memory: 3912kb

input:

output:

1277.1333333333

result:

wrong answer read 1277.133333333 but expected 1021.333333333, error = 255.800000000

Subtask #5:

score: 0

Wrong Answer

Test #61:

score: 33

Accepted

time: 0ms

memory: 4308kb

input:

output:

324.3333333333

result:

ok error = 0.000000000

Test #62:

score: 0

Wrong Answer

time: 1ms

memory: 4228kb

input:

output:

7812.0000000000

result:

wrong answer read 7812.000000000 but expected 1892.320526696, error = 5919.679473304

Subtask #6:

score: 11

Accepted

Test #81:

score: 11

Accepted

time: 10ms

memory: 5764kb

input:

output:

1767.1975007973

result:

ok error = 0.000000000

Test #82:

score: 11

Accepted

time: 8ms

memory: 5896kb

input:

output:

2763.3815674113

result:

ok error = 0.000000000

Test #83:

score: 11

Accepted

time: 5ms

memory: 5676kb

input:

output:

3763.0435188736

result:

ok error = 0.000000000

Test #84:

score: 11

Accepted

time: 8ms

memory: 5916kb

input:

output:

4840.5411729334

result:

ok error = 0.000000000

Test #85:

score: 11

Accepted

time: 8ms

memory: 5912kb

input:

output:

5820.4909981528

result:

ok error = 0.000000000

Test #86:

score: 11

Accepted

time: 13ms

memory: 5876kb

input:

output:

3946.9244817827

result:

ok error = 0.000000000

Test #87:

score: 11

Accepted

time: 8ms

memory: 5896kb

input:

output:

3878.5527203058

result:

ok error = 0.000000000

Subtask #7:

score: 23

Accepted

Test #88:

score: 23

Accepted

time: 0ms

memory: 5836kb

input:

output:

368.1297619048

result:

ok error = 0.000000000

Test #89:

score: 23

Accepted

time: 3ms

memory: 5828kb

input:

output:

2882.4745823040

result:

ok error = 0.000000000

Test #90:

score: 23

Accepted

time: 2ms

memory: 5868kb

input:

output:

641.5151181260

result:

ok error = 0.000000000

Test #91:

score: 23

Accepted

time: 2ms

memory: 5676kb

input:

output:

3543.8836038744

result:

ok error = 0.000000000

Test #92:

score: 23

Accepted

time: 11ms

memory: 5772kb

input:

output:

955.8861020681

result:

ok error = 0.000000000

Test #93:

score: 23

Accepted

time: 3ms

memory: 5828kb

input:

output:

4225.9687876561

result:

ok error = 0.000000000

Test #94:

score: 23

Accepted

time: 13ms

memory: 5896kb

input:

output:

1459.5140837496

result:

ok error = 0.000000000

Test #95:

score: 23

Accepted

time: 8ms

memory: 5812kb

input:

output:

4543.5172691461

result:

ok error = 0.000000000

Test #96:

score: 23

Accepted

time: 10ms

memory: 5864kb

input:

output:

1503.7968079258

result:

ok error = 0.000000000

Test #97:

score: 23

Accepted

time: 8ms

memory: 5900kb

input:

output:

4679.3552447889

result:

ok error = 0.000000000

Test #98:

score: 23

Accepted

time: 15ms

memory: 5820kb

input:

output:

3006.7652979011

result:

ok error = 0.000000000

Test #99:

score: 23

Accepted

time: 19ms

memory: 5808kb

input:

output:

3767.2089795903

result:

ok error = 0.000000000

Test #100:

score: 23

Accepted

time: 14ms

memory: 5820kb

input:

output:

3691.7046047957

result:

ok error = 0.000000000

Test #101:

score: 23

Accepted

time: 11ms

memory: 5916kb

input:

output:

3489.9814632569

result:

ok error = 0.000000000

Test #102:

score: 23

Accepted

time: 4ms

memory: 5872kb

input:

output:

3505.9720675481

result:

ok error = 0.000000000

Test #103:

score: 23

Accepted

time: 7ms

memory: 5868kb

input:

output:

3562.0854954342

result:

ok error = 0.000000000

Test #104:

score: 23

Accepted

time: 8ms

memory: 5876kb

input:

output:

3476.2567559925

result:

ok error = 0.000000000

Test #105:

score: 23

Accepted

time: 10ms

memory: 5896kb

input:

output:

350.0000000000

result:

ok error = 0.000000000