QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#130623	#2629. Let's Win the Election	251Sec	23	597ms	9876kb	C++14	1.4kb	2023-07-24 17:44:37	2023-07-24 17:44:40

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-24 17:44:40]
评测

测评结果：23
用时：597ms
内存：9876kb

查看

[2023-07-24 17:44:37]
提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld inf = 1e18;
int n, k;
struct Node {
    ll a, b;
} v[505];
ld f[505][505];
ll g[505][505];
ld ans;
bool CmpB(const Node &x, const Node &y) {
    return x.b < y.b;
}
bool CmpA(const Node &x, const Node &y) {
    return x.a < y.a;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &v[i].a, &v[i].b);
        if (v[i].b == -1) v[i].b = 1e18;
    }
    ans = inf;
    for (int i = 1; i <= n; i++) {
        sort(v + 1, v + n + 1, CmpB);
        sort(v + i, v + n + 1, CmpA);
        for (int j = i; j <= n; j++) g[i][j] = g[i][j - 1] + v[j].a;
    }
    sort(v + 1, v + n + 1, CmpB);
    for (int pre = 0; pre <= n; pre++) {
        for (int i = 0; i < 505; i++) {
            for (int j = 0; j < 505; j++) {
                f[i][j] = 1e18;
            }
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= pre; j++) {
                f[i][j] = min(f[i][j], f[i - 1][j] + 1.0 * v[i].a / (pre + 1));
                if (j) f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1.0 * v[i].b / j);
            }
        }
        for (int i = pre; i <= n; i++) ans = min(ans, 1.0 * g[i + 1][k] / (pre + 1) + f[i][pre]);
    }
    printf("%.15Lf", ans);
    return 0;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 5

Accepted

time: 4ms

memory: 8984kb

input:

1
1
729 -1

output:

729.000000000000000

result:

ok error = 0.000000000

Test #2:

score: 0

Accepted

time: 2ms

memory: 8988kb

input:

output:

300.000000000000000

result:

ok error = 0.000000000

Test #3:

score: 0

Accepted

time: 2ms

memory: 9132kb

input:

output:

1140.000000000000000

result:

ok error = 0.000000000

Test #4:

score: 0

Accepted

time: 5ms

memory: 9216kb

input:

output:

1059.000000000000000

result:

ok error = 0.000000000

Test #5:

score: 0

Accepted

time: 589ms

memory: 9764kb

input:

output:

2580.000000000000000

result:

ok error = 0.000000000

Test #6:

score: 0

Accepted

time: 586ms

memory: 9756kb

input:

output:

15729.000000000000000

result:

ok error = 0.000000000

Test #7:

score: -5

Wrong Answer

time: 588ms

memory: 9828kb

input:

output:

56061.000000000000000

result:

wrong answer read 56061.000000000 but expected 66687.000000000, error = 10626.000000000

Subtask #2:

score: 0

Wrong Answer

Test #11:

score: 5

Accepted

time: 3ms

memory: 7876kb

input:

1
1
791 791

output:

791.000000000000000

result:

ok error = 0.000000000

Test #12:

score: 0

Accepted

time: 586ms

memory: 9608kb

input:

output:

341.079314578951176

result:

ok error = 0.000000000

Test #13:

score: 0

Accepted

time: 590ms

memory: 9700kb

input:

output:

355.342286415133880

result:

ok error = 0.000000000

Test #14:

score: 0

Accepted

time: 588ms

memory: 9628kb

input:

output:

940.689688879509461

result:

ok error = 0.000000000

Test #15:

score: 0

Accepted

time: 579ms

memory: 9632kb

input:

output:

707.046228150463193

result:

ok error = 0.000000000

Test #16:

score: 0

Accepted

time: 591ms

memory: 9768kb

input:

output:

982.134559205841727

result:

ok error = 0.000000000

Test #17:

score: -5

Wrong Answer

time: 591ms

memory: 9760kb

input:

output:

1761.403063650056000

result:

wrong answer read 1761.403063650 but expected 1956.186568805, error = 194.783505155

Subtask #3:

score: 11

Accepted

Test #21:

score: 11

Accepted

time: 7ms

memory: 8616kb

input:

output:

51.000000000000000

result:

ok error = 0.000000000

Test #22:

score: 0

Accepted

time: 2ms

memory: 8824kb

input:

output:

68.000000000000000

result:

ok error = 0.000000000

Test #23:

score: 0

Accepted

time: 6ms

memory: 8216kb

input:

output:

301.500000000000000

result:

ok error = 0.000000000

Test #24:

score: 0

Accepted

time: 7ms

memory: 9800kb

input:

output:

589.500000000000000

result:

ok error = 0.000000000

Test #25:

score: 0

Accepted

time: 7ms

memory: 9532kb

input:

output:

517.000000000000000

result:

ok error = 0.000000000

Test #26:

score: 0

Accepted

time: 6ms

memory: 8192kb

input:

output:

901.000000000000000

result:

ok error = 0.000000000

Test #27:

score: 0

Accepted

time: 6ms

memory: 8136kb

input:

output:

942.083333333333343

result:

ok error = 0.000000000

Test #28:

score: 0

Accepted

time: 3ms

memory: 9572kb

input:

output:

881.000000000000000

result:

ok error = 0.000000000

Test #29:

score: 0

Accepted

time: 6ms

memory: 8372kb

input:

output:

1258.500000000000000

result:

ok error = 0.000000000

Test #30:

score: 0

Accepted

time: 6ms

memory: 8452kb

input:

output:

1495.833333333333286

result:

ok error = 0.000000000

Test #31:

score: 0

Accepted

time: 6ms

memory: 7684kb

input:

output:

1505.250000000000000

result:

ok error = 0.000000000

Test #32:

score: 0

Accepted

time: 6ms

memory: 7980kb

input:

output:

1232.916666666666657

result:

ok error = 0.000000000

Test #33:

score: 0

Accepted

time: 7ms

memory: 9272kb

input:

output:

958.500000000000000

result:

ok error = 0.000000000

Test #34:

score: 0

Accepted

time: 5ms

memory: 8188kb

input:

output:

1023.333333333333314

result:

ok error = 0.000000000

Test #35:

score: 0

Accepted

time: 3ms

memory: 9308kb

input:

output:

1369.333333333333343

result:

ok error = 0.000000000

Subtask #4:

score: 12

Accepted

Test #36:

score: 12

Accepted

time: 14ms

memory: 8472kb

input:

output:

112.000000000000000

result:

ok error = 0.000000000

Test #37:

score: 0

Accepted

time: 14ms

memory: 8476kb

input:

output:

372.916666666666664

result:

ok error = 0.000000000

Test #38:

score: 0

Accepted

time: 14ms

memory: 7732kb

input:

output:

1021.333333333333343

result:

ok error = 0.000000000

Test #39:

score: 0

Accepted

time: 8ms

memory: 8048kb

input:

output:

719.499999999999979

result:

ok error = 0.000000000

Test #40:

score: 0

Accepted

time: 14ms

memory: 9352kb

input:

output:

997.530952380952371

result:

ok error = 0.000000000

Test #41:

score: 0

Accepted

time: 14ms

memory: 8912kb

input:

output:

1174.007142857142830

result:

ok error = 0.000000000

Test #42:

score: 0

Accepted

time: 14ms

memory: 9440kb

input:

output:

1127.883333333333361

result:

ok error = 0.000000000

Test #43:

score: 0

Accepted

time: 11ms

memory: 9092kb

input:

output:

1750.599999999999980

result:

ok error = 0.000000000

Test #44:

score: 0

Accepted

time: 11ms

memory: 9036kb

input:

output:

716.616666666666646

result:

ok error = 0.000000000

Test #45:

score: 0

Accepted

time: 11ms

memory: 9700kb

input:

output:

1160.706818181818186

result:

ok error = 0.000000000

Test #46:

score: 0

Accepted

time: 14ms

memory: 8044kb

input:

output:

1727.104345654345684

result:

ok error = 0.000000000

Test #47:

score: 0

Accepted

time: 8ms

memory: 8400kb

input:

output:

569.000000000000000

result:

ok error = 0.000000000

Test #48:

score: 0

Accepted

time: 14ms

memory: 7952kb

input:

output:

1779.500000000000000

result:

ok error = 0.000000000

Test #49:

score: 0

Accepted

time: 14ms

memory: 8120kb

input:

output:

1790.816666666666634

result:

ok error = 0.000000000

Test #50:

score: 0

Accepted

time: 11ms

memory: 9008kb

input:

output:

1657.024747474747464

result:

ok error = 0.000000000

Test #51:

score: 0

Accepted

time: 15ms

memory: 9432kb

input:

output:

1861.583333333333343

result:

ok error = 0.000000000

Test #52:

score: 0

Accepted

time: 15ms

memory: 7664kb

input:

output:

1661.055122655122631

result:

ok error = 0.000000000

Test #53:

score: 0

Accepted

time: 15ms

memory: 9620kb

input:

output:

1676.966666666666654

result:

ok error = 0.000000000

Test #54:

score: 0

Accepted

time: 14ms

memory: 8880kb

input:

output:

1705.379761904761907

result:

ok error = 0.000000000

Test #55:

score: 0

Accepted

time: 11ms

memory: 9040kb

input:

output:

1853.293650793650826

result:

ok error = 0.000000000

Test #56:

score: 0

Accepted

time: 14ms

memory: 8024kb

input:

output:

1701.451587301587303

result:

ok error = 0.000000000

Test #57:

score: 0

Accepted

time: 11ms

memory: 9008kb

input:

output:

1784.726570651570675

result:

ok error = 0.000000000

Test #58:

score: 0

Accepted

time: 14ms

memory: 8740kb

input:

output:

1733.104329004328982

result:

ok error = 0.000000000

Test #59:

score: 0

Accepted

time: 14ms

memory: 9536kb

input:

output:

2064.847768897768901

result:

ok error = 0.000000000

Test #60:

score: 0

Accepted

time: 10ms

memory: 8900kb

input:

output:

1816.244047619047620

result:

ok error = 0.000000000

Subtask #5:

score: 0

Wrong Answer

Test #61:

score: 33

Accepted

time: 63ms

memory: 8288kb

input:

output:

324.333333333333314

result:

ok error = 0.000000000

Test #62:

score: 0

Accepted

time: 64ms

memory: 9364kb

input:

output:

1892.320526695526688

result:

ok error = 0.000000000

Test #63:

score: 0

Accepted

time: 60ms

memory: 9580kb

input:

output:

646.342857142857145

result:

ok error = 0.000000000

Test #64:

score: 0

Accepted

time: 59ms

memory: 8776kb

input:

output:

2424.850311079529369

result:

ok error = 0.000000000

Test #65:

score: 0

Accepted

time: 60ms

memory: 9192kb

input:

output:

2866.678922813421719

result:

ok error = 0.000000000

Test #66:

score: 0

Accepted

time: 63ms

memory: 8156kb

input:

output:

945.437089638947204

result:

ok error = 0.000000000

Test #67:

score: 0

Accepted

time: 56ms

memory: 9092kb

input:

output:

984.344500039004694

result:

ok error = 0.000000000

Test #68:

score: 0

Accepted

time: 63ms

memory: 9644kb

input:

output:

3132.964757953951635

result:

ok error = 0.000000000

Test #69:

score: 0

Accepted

time: 63ms

memory: 8232kb

input:

output:

3152.911064279477616

result:

ok error = 0.000000000

Test #70:

score: 0

Accepted

time: 59ms

memory: 8104kb

input:

output:

1227.611843732420540

result:

ok error = 0.000000000

Test #71:

score: 0

Accepted

time: 59ms

memory: 8936kb

input:

output:

1732.025922971384037

result:

ok error = 0.000000000

Test #72:

score: -33

Wrong Answer

time: 56ms

memory: 8560kb

input:

output:

3447.884429528074227

result:

wrong answer read 3447.884429528 but expected 3448.021415829, error = 0.136986301

Subtask #6:

score: 0

Wrong Answer

Test #81:

score: 11

Accepted

time: 591ms

memory: 9620kb

input:

output:

1767.197500797273273

result:

ok error = 0.000000000

Test #82:

score: 0

Accepted

time: 593ms

memory: 9600kb

input:

output:

2763.381567411287206

result:

ok error = 0.000000000

Test #83:

score: 0

Accepted

time: 590ms

memory: 9604kb

input:

output:

3763.043518873627175

result:

ok error = 0.000000000

Test #84:

score: 0

Accepted

time: 589ms

memory: 9860kb

input:

output:

4840.541172933354444

result:

ok error = 0.000000000

Test #85:

score: 0

Accepted

time: 592ms

memory: 9648kb

input:

output:

5820.490998152771430

result:

ok error = 0.000000000

Test #86:

score: -11

Wrong Answer

time: 597ms

memory: 9732kb

input:

output:

3946.203957765200792

result:

wrong answer read 3946.203957765 but expected 3946.924481783, error = 0.720524017

Subtask #7:

score: 0

Wrong Answer

Test #88:

score: 23

Accepted

time: 589ms

memory: 9632kb

input:

output:

368.129761904761910

result:

ok error = 0.000000000

Test #89:

score: 0

Accepted

time: 596ms

memory: 9876kb

input:

output:

2882.474582304018220

result:

ok error = 0.000000000

Test #90:

score: 0

Accepted

time: 591ms

memory: 9604kb

input:

output:

641.515118125953357

result:

ok error = 0.000000000

Test #91:

score: 0

Accepted

time: 595ms

memory: 9652kb

input:

output:

3543.883603874394638

result:

ok error = 0.000000000

Test #92:

score: -23

Wrong Answer

time: 596ms

memory: 9624kb

input:

output:

954.687280317703023

result:

wrong answer read 954.687280318 but expected 955.886102068, error = 1.198821750