QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#670924	#2629. Let's Win the Election	liuziao^#	61	1518ms	7892kb	C++23	2.1kb	2024-10-24 08:50:37	2024-10-24 08:50:37

Judging History

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

[2024-10-24 08:50:37]
评测

测评结果：61
用时：1518ms
内存：7892kb

查看

[2024-10-24 08:50:37]
提交

answer

#include <bits/stdc++.h>

// #define int int64_t

using f64 = long 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) {
  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));
      }
    }
  }
  return f[cnt][k - cnt];
}

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: 3932kb

input:

1
1
729 -1

output:

729.0000000000

result:

ok error = 0.000000000

Test #2:

score: 5

Accepted

time: 0ms

memory: 3900kb

input:

output:

300.0000000000

result:

ok error = 0.000000000

Test #3:

score: 5

Accepted

time: 0ms

memory: 3832kb

input:

output:

1140.0000000000

result:

ok error = 0.000000000

Test #4:

score: 5

Accepted

time: 1ms

memory: 5988kb

input:

output:

1059.0000000000

result:

ok error = 0.000000000

Test #5:

score: 5

Accepted

time: 0ms

memory: 7780kb

input:

output:

2580.0000000000

result:

ok error = 0.000000000

Test #6:

score: 5

Accepted

time: 2ms

memory: 7608kb

input:

output:

15729.0000000000

result:

ok error = 0.000000000

Test #7:

score: 5

Accepted

time: 2ms

memory: 7756kb

input:

output:

66687.0000000000

result:

ok error = 0.000000000

Test #8:

score: 5

Accepted

time: 3ms

memory: 7772kb

input:

output:

147876.0000000000

result:

ok error = 0.000000000

Test #9:

score: 5

Accepted

time: 0ms

memory: 7836kb

input:

output:

249562.0000000000

result:

ok error = 0.000000000

Test #10:

score: 5

Accepted

time: 2ms

memory: 7772kb

input:

output:

350000.0000000000

result:

ok error = 0.000000000

Subtask #2:

score: 0

Time Limit Exceeded

Test #11:

score: 5

Accepted

time: 0ms

memory: 3772kb

input:

1
1
791 791

output:

791.0000000000

result:

ok error = 0.000000000

Test #12:

score: 5

Accepted

time: 139ms

memory: 7776kb

input:

output:

341.0793145790

result:

ok error = 0.000000000

Test #13:

score: 5

Accepted

time: 256ms

memory: 7712kb

input:

output:

355.3422864151

result:

ok error = 0.000000000

Test #14:

score: 5

Accepted

time: 174ms

memory: 7836kb

input:

output:

940.6896888795

result:

ok error = 0.000000000

Test #15:

score: 5

Accepted

time: 684ms

memory: 7892kb

input:

output:

707.0462281505

result:

ok error = 0.000000000

Test #16:

score: 5

Accepted

time: 1518ms

memory: 7848kb

input:

output:

982.1345592058

result:

ok error = 0.000000000

Test #17:

score: 5

Accepted

time: 786ms

memory: 7848kb

input:

output:

1956.1865688047

result:

ok error = 0.000000000

Test #18:

score: 5

Accepted

time: 1367ms

memory: 7844kb

input:

output:

1043.2370845765

result:

ok error = 0.000000000

Test #19:

score: 0

Time Limit Exceeded

input:

output:

result:

Subtask #3:

score: 11

Accepted

Test #21:

score: 11

Accepted

time: 0ms

memory: 3908kb

input:

output:

51.0000000000

result:

ok error = 0.000000000

Test #22:

score: 11

Accepted

time: 0ms

memory: 3848kb

input:

output:

68.0000000000

result:

ok error = 0.000000000

Test #23:

score: 11

Accepted

time: 0ms

memory: 3728kb

input:

output:

301.5000000000

result:

ok error = 0.000000000

Test #24:

score: 11

Accepted

time: 0ms

memory: 3848kb

input:

output:

589.5000000000

result:

ok error = 0.000000000

Test #25:

score: 11

Accepted

time: 0ms

memory: 3920kb

input:

output:

517.0000000000

result:

ok error = 0.000000000

Test #26:

score: 11

Accepted

time: 0ms

memory: 3924kb

input:

output:

901.0000000000

result:

ok error = 0.000000000

Test #27:

score: 11

Accepted

time: 0ms

memory: 3908kb

input:

output:

942.0833333333

result:

ok error = 0.000000000

Test #28:

score: 11

Accepted

time: 0ms

memory: 3760kb

input:

output:

881.0000000000

result:

ok error = 0.000000000

Test #29:

score: 11

Accepted

time: 0ms

memory: 3928kb

input:

output:

1258.5000000000

result:

ok error = 0.000000000

Test #30:

score: 11

Accepted

time: 0ms

memory: 3848kb

input:

output:

1495.8333333333

result:

ok error = 0.000000000

Test #31:

score: 11

Accepted

time: 0ms

memory: 3960kb

input:

output:

1505.2500000000

result:

ok error = 0.000000000

Test #32:

score: 11

Accepted

time: 0ms

memory: 3912kb

input:

output:

1232.9166666667

result:

ok error = 0.000000000

Test #33:

score: 11

Accepted

time: 0ms

memory: 3856kb

input:

output:

958.5000000000

result:

ok error = 0.000000000

Test #34:

score: 11

Accepted

time: 0ms

memory: 3808kb

input:

output:

1023.3333333333

result:

ok error = 0.000000000

Test #35:

score: 11

Accepted

time: 0ms

memory: 3852kb

input:

output:

1369.3333333333

result:

ok error = 0.000000000

Subtask #4:

score: 12

Accepted

Test #36:

score: 12

Accepted

time: 0ms

memory: 3964kb

input:

output:

112.0000000000

result:

ok error = 0.000000000

Test #37:

score: 12

Accepted

time: 0ms

memory: 3892kb

input:

output:

372.9166666667

result:

ok error = 0.000000000

Test #38:

score: 12

Accepted

time: 0ms

memory: 3908kb

input:

output:

1021.3333333333

result:

ok error = 0.000000000

Test #39:

score: 12

Accepted

time: 0ms

memory: 3968kb

input:

output:

719.5000000000

result:

ok error = 0.000000000

Test #40:

score: 12

Accepted

time: 0ms

memory: 3876kb

input:

output:

997.5309523810

result:

ok error = 0.000000000

Test #41:

score: 12

Accepted

time: 1ms

memory: 3944kb

input:

output:

1174.0071428571

result:

ok error = 0.000000000

Test #42:

score: 12

Accepted

time: 0ms

memory: 3860kb

input:

output:

1127.8833333333

result:

ok error = 0.000000000

Test #43:

score: 12

Accepted

time: 0ms

memory: 3972kb

input:

output:

1750.6000000000

result:

ok error = 0.000000000

Test #44:

score: 12

Accepted

time: 0ms

memory: 3916kb

input:

output:

716.6166666667

result:

ok error = 0.000000000

Test #45:

score: 12

Accepted

time: 1ms

memory: 4024kb

input:

output:

1160.7068181818

result:

ok error = 0.000000000

Test #46:

score: 12

Accepted

time: 1ms

memory: 3988kb

input:

output:

1727.1043456543

result:

ok error = 0.000000000

Test #47:

score: 12

Accepted

time: 0ms

memory: 3908kb

input:

output:

569.0000000000

result:

ok error = 0.000000000

Test #48:

score: 12

Accepted

time: 0ms

memory: 3972kb

input:

output:

1779.5000000000

result:

ok error = 0.000000000

Test #49:

score: 12

Accepted

time: 0ms

memory: 3984kb

input:

output:

1790.8166666667

result:

ok error = 0.000000000

Test #50:

score: 12

Accepted

time: 0ms

memory: 3908kb

input:

output:

1657.0247474747

result:

ok error = 0.000000000

Test #51:

score: 12

Accepted

time: 1ms

memory: 6000kb

input:

output:

1861.5833333333

result:

ok error = 0.000000000

Test #52:

score: 12

Accepted

time: 0ms

memory: 3924kb

input:

output:

1661.0551226551

result:

ok error = 0.000000000

Test #53:

score: 12

Accepted

time: 1ms

memory: 3972kb

input:

output:

1676.9666666667

result:

ok error = 0.000000000

Test #54:

score: 12

Accepted

time: 0ms

memory: 4020kb

input:

output:

1705.3797619048

result:

ok error = 0.000000000

Test #55:

score: 12

Accepted

time: 0ms

memory: 3984kb

input:

output:

1853.2936507937

result:

ok error = 0.000000000

Test #56:

score: 12

Accepted

time: 0ms

memory: 3860kb

input:

output:

1701.4515873016

result:

ok error = 0.000000000

Test #57:

score: 12

Accepted

time: 0ms

memory: 3912kb

input:

output:

1784.7265706516

result:

ok error = 0.000000000

Test #58:

score: 12

Accepted

time: 0ms

memory: 3892kb

input:

output:

1733.1043290043

result:

ok error = 0.000000000

Test #59:

score: 12

Accepted

time: 0ms

memory: 3964kb

input:

output:

2064.8477688978

result:

ok error = 0.000000000

Test #60:

score: 12

Accepted

time: 0ms

memory: 3788kb

input:

output:

1816.2440476190

result:

ok error = 0.000000000

Subtask #5:

score: 33

Accepted

Test #61:

score: 33

Accepted

time: 0ms

memory: 4372kb

input:

output:

324.3333333333

result:

ok error = 0.000000000

Test #62:

score: 33

Accepted

time: 0ms

memory: 6132kb

input:

output:

1892.3205266955

result:

ok error = 0.000000000

Test #63:

score: 33

Accepted

time: 3ms

memory: 4464kb

input:

output:

646.3428571429

result:

ok error = 0.000000000

Test #64:

score: 33

Accepted

time: 3ms

memory: 4392kb

input:

output:

2424.8503110795

result:

ok error = 0.000000000

Test #65:

score: 33

Accepted

time: 7ms

memory: 6112kb

input:

output:

2866.6789228134

result:

ok error = 0.000000000

Test #66:

score: 33

Accepted

time: 6ms

memory: 6096kb

input:

output:

945.4370896389

result:

ok error = 0.000000000

Test #67:

score: 33

Accepted

time: 11ms

memory: 6268kb

input:

output:

984.3445000390

result:

ok error = 0.000000000

Test #68:

score: 33

Accepted

time: 7ms

memory: 5936kb

input:

output:

3132.9647579540

result:

ok error = 0.000000000

Test #69:

score: 33

Accepted

time: 18ms

memory: 6292kb

input:

output:

3152.9110642795

result:

ok error = 0.000000000

Test #70:

score: 33

Accepted

time: 16ms

memory: 4268kb

input:

output:

1227.6118437324

result:

ok error = 0.000000000

Test #71:

score: 33

Accepted

time: 30ms

memory: 4456kb

input:

output:

1732.0259229714

result:

ok error = 0.000000000

Test #72:

score: 33

Accepted

time: 22ms

memory: 6368kb

input:

output:

3448.0214158294

result:

ok error = 0.000000000

Test #73:

score: 33

Accepted

time: 8ms

memory: 4392kb

input:

output:

2854.2723304473

result:

ok error = 0.000000000

Test #74:

score: 33

Accepted

time: 8ms

memory: 6444kb

input:

output:

2704.4200840421

result:

ok error = 0.000000000

Test #75:

score: 33

Accepted

time: 11ms

memory: 4268kb

input:

output:

2421.8092932050

result:

ok error = 0.000000000

Test #76:

score: 33

Accepted

time: 9ms

memory: 4472kb

input:

output:

2114.6567973693

result:

ok error = 0.000000000

Test #77:

score: 33

Accepted

time: 12ms

memory: 4400kb

input:

output:

2666.0489753128

result:

ok error = 0.000000000

Test #78:

score: 33

Accepted

time: 6ms

memory: 6504kb

input:

output:

2807.7078472080

result:

ok error = 0.000000000

Test #79:

score: 33

Accepted

time: 6ms

memory: 4460kb

input:

output:

2610.9578556339

result:

ok error = 0.000000000

Test #80:

score: 33

Accepted

time: 12ms

memory: 4396kb

input:

output:

2656.8567465914

result:

ok error = 0.000000000

Subtask #6:

score: 0

Time Limit Exceeded

Test #81:

score: 0

Time Limit Exceeded

input:

output:

result:

Subtask #7:

score: 0

Time Limit Exceeded

Test #88:

score: 23

Accepted

time: 30ms

memory: 7840kb

input:

output:

368.1297619048

result:

ok error = 0.000000000

Test #89:

score: 23

Accepted

time: 32ms

memory: 7784kb

input:

output:

2882.4745823040

result:

ok error = 0.000000000

Test #90:

score: 23

Accepted

time: 215ms

memory: 7772kb

input:

output:

641.5151181260

result:

ok error = 0.000000000

Test #91:

score: 23

Accepted

time: 177ms

memory: 7648kb

input:

output:

3543.8836038744

result:

ok error = 0.000000000

Test #92:

score: 23

Accepted

time: 980ms

memory: 7840kb

input:

output:

955.8861020681

result:

ok error = 0.000000000

Test #93:

score: 23

Accepted

time: 782ms

memory: 7644kb

input:

output:

4225.9687876561

result:

ok error = 0.000000000

Test #94:

score: 0

Time Limit Exceeded

input: