QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#104998	#6387. Burgers	Bucketsmith^#	51	19ms	4840kb	C++17	855b	2023-05-12 18:45:06	2024-05-26 02:53:29

Judging History

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

[2024-05-26 02:53:29]
评测

测评结果：51
用时：19ms
内存：4840kb

查看

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

[2023-05-12 18:45:06]
提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, x[N], a[N], b[N];

double check(double c) {
    double ret = 1e9 + 7;
    for(int i = 1; i <= n; i ++) {
        if(a[i] * c > x[i]) return -1;
        ret = min(ret, (x[i] - a[i] * c) / b[i]);
    }
    return c + ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> x[i];
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];

    double l = 0, r = 1e9 + 7;
    for(int i = 1; i <= n; i ++)
        r = min(r, x[i] * 1.0 / a[i]);
    
    while(l + 2 < r) {
        int m1 = (l + r) / 2, m2 = m1 + 1;
        if(check(m1) <= check(m2)) l = m1;
        else r = m2;
    }
    cout << (int)max(check(floor(l)), check(ceil(l)));

}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 9

Accepted

Test #1:

score: 9

Accepted

time: 19ms

memory: 4840kb

input:

100000
832959141 860554021 862795346 837477909 827080541 943401363 856243490 930836466 825832073 817675119 948472447 961350173 842023597 850294389 992113408 830841958 871439399 837208944 907679706 962378151 845055149 928095307 886589127 999818483 957139336 812990090 960097526 915292011 896734097 804...

output:

266669433

result:

ok single line: '266669433'

Test #2:

score: 0

Accepted

time: 19ms

memory: 4824kb

input:

100000
801425346 886729013 890115095 965862324 949313211 967125997 830492788 949962384 880125881 940181745 951464973 829279861 895810042 834420389 834129226 996922620 825147557 821630755 868774231 996277414 951398806 804596196 861909938 866687678 886611115 882461062 871167279 870520446 940022159 987...

output:

16001074

result:

ok single line: '16001074'

Test #3:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

output:

result:

ok single line: '29'

Subtask #2:

score: 17

Accepted

Test #4:

score: 17

Accepted

time: 0ms

memory: 3596kb

input:

100
85 93 68 69 67 74 92 99 68 81 78 62 88 73 70 87 91 78 63 60 72 86 72 88 97 96 80 96 79 81 88 67 71 68 82 61 62 65 72 96 66 95 89 61 61 74 63 89 83 99 85 92 85 61 99 96 94 63 91 64 79 84 95 64 77 89 78 83 72 98 83 90 78 63 91 100 77 82 71 78 65 60 74 76 97 94 97 69 73 97 82 96 88 66 91 69 89 65 6...

output:

result:

ok single line: '0'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

output:

result:

ok single line: '38'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

output:

result:

ok single line: '37'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

100
61 69 60 67 70 63 71 83 80 66 93 67 85 95 82 87 71 92 66 71 92 74 95 60 65 87 97 60 76 75 76 76 87 75 86 83 96 85 74 98 64 86 84 100 83 68 62 84 69 73 62 75 91 87 90 68 83 90 72 96 76 97 73 76 98 99 91 94 72 76 66 85 75 76 72 71 86 81 95 87 61 75 66 77 89 86 87 91 79 73 80 70 77 89 73 86 91 90 6...

output:

result:

ok single line: '10'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

100
95 60 65 66 62 93 90 100 91 67 80 81 81 90 83 72 100 88 75 89 97 74 62 70 94 74 99 68 91 90 91 75 100 69 83 95 92 92 86 67 82 90 93 87 96 98 94 96 88 80 60 90 76 88 68 70 90 62 75 64 82 73 92 72 100 80 60 87 78 100 69 61 95 85 94 73 89 88 87 79 87 99 98 85 63 82 92 75 87 94 81 61 91 88 97 72 69 ...

output:

result:

ok single line: '3'

Subtask #3:

score: 25

Accepted

Dependency #2:

100%

Accepted

Test #9:

score: 25

Accepted

time: 1ms

memory: 3620kb

input:

1500
1026 1183 1359 930 1007 1051 1371 1388 1330 1121 1257 1136 1127 1418 1424 1213 904 1418 1256 1360 943 1482 1066 1059 1142 1270 1497 1231 1260 1207 1086 1473 945 1423 1165 1441 1099 1430 1340 1461 1378 1005 1096 1085 1204 1392 916 928 1385 1304 1111 1097 935 1045 1344 996 1024 1057 904 1052 1355...

output:

result:

ok single line: '303'

Test #10:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

1500
1180 1370 936 1246 1284 1015 1288 1117 1067 927 1223 1326 943 987 1178 1007 1012 1049 1190 1169 1400 1351 1023 1138 1076 979 924 924 1274 1246 1074 999 1041 1428 1258 1020 1497 1255 1237 1052 1237 1050 1422 1051 1297 1328 1173 1069 1086 1319 925 1480 1452 1152 1008 1168 1445 1187 998 1059 1190 ...

output:

result:

ok single line: '0'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

output:

result:

ok single line: '508'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3596kb

input:

3
1432 1350 1332
2 3 1
1 2 2

output:

result:

ok single line: '670'

Test #13:

score: 0

Accepted

time: 1ms

memory: 3740kb

input:

1500
1443 1487 1442 1409 1404 1463 1463 1483 1455 1487 1419 1402 1440 1468 1463 1465 1405 1477 1422 1462 1484 1493 1455 1490 1453 1402 1478 1459 1441 1415 1409 1476 1459 1413 1462 1458 1444 1402 1411 1441 1433 1409 1460 1431 1402 1428 1439 1484 1425 1489 1466 1427 1448 1462 1406 1429 1402 1404 1433 ...

output:

result:

ok single line: '700'

Subtask #4:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #14:

score: 49

Accepted

time: 0ms

memory: 3656kb

input:

2
354342446 199816239
87138 26386
89618 68706

output:

result:

ok single line: '4066'

Test #15:

score: -49

Wrong Answer

time: 0ms

memory: 3672kb

input:

2
997439741 934240087
7262852 4990954
17150312 18264464

output:

result:

wrong answer 1st lines differ - expected: '137', found: '136'