QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #283648 | #676. Travelling Merchant | TedLee | 100 ✓ | 102ms | 5388kb | C++14 | 3.3kb | 2023-12-15 00:37:46 | 2023-12-15 00:37:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const long long M = 1e10;
const long long minfinite = -1e10;
int n, m, k;
void floyd_warshall(vector<vector<pii>>& adj, vector<vector<long long>>& d) {
for(int i=1;i<=n;i++) {
d[i][i] = 0;
}
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
void get_profit(vector<vector<long long>>& bs_list, vector<vector<long long>>& profit) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int g=0;g<k;g++) {
if(bs_list[i][g*2] == -1 || bs_list[j][g*2+1] == -1) continue;
profit[i][j] = max(profit[i][j], bs_list[j][g*2+1] - bs_list[i][g*2]);
}
}
}
}
bool check(int x, vector<vector<long long>> &profit, vector<vector<long long>>& d) {
// cout << "check " << x <<endl;
vector<vector<long long>> adj(n+1, vector<long long>(n+1, -M));
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(d[i][j] == M)
adj[i][j] = -M;
else if(i == j)
adj[i][j] = -M;
else
adj[i][j] = profit[i][j] - x*d[i][j];
}
}
// for(int i=1;i<=n;i++) {
// for(int j=1;j<=n;j++) {
// cout << adj[i][j] << " \n"[j==n];
// }
// }
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
adj[i][j] = max(adj[i][j], adj[i][k] + adj[k][j]);
if(adj[i][i] >= 0) return true;
}
}
}
for(int k=1;k<=n;k++) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(adj[i][j] < adj[i][k] + adj[k][j]) return true;
}
}
}
return false;
}
pii bn_search(int L, int R, vector<vector<long long>> &profit, vector<vector<long long>>& d) {
if(!check(L, profit, d)) return {L-1, L};
if(check(R, profit, d)) return {R, R+1};
while(R-L > 1) {
int m = L + (R-L)/2;
if(check(m, profit, d))
L = m;
else
R = m;
}
return {L, R};
}
int main(){
cin >> n >> m >> k;
vector<vector<long long>> bs_list(n+1, vector<long long>(2*k));
vector<vector<pii>> adj(n+1);
vector<vector<long long>> d(n+1, vector<long long>(n+1, M));
for(int i=1;i<=n;i++) {
for(int j=0;j<k;j++) {
int b, s;
cin >> b >> s;
bs_list[i][j*2] = b;
bs_list[i][j*2+1] = s;
}
}
for(int i=0;i<m;i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
d[u][v] = w;
}
floyd_warshall(adj, d);
vector<vector<long long>> profit(n+1, vector<long long>(n+1, 0));
get_profit(bs_list, profit);
// puts("profit");
// for(int i=1;i<=n;i++) {
// for(int j=1;j<=n;j++) {
// cout << profit[i][j] << " \n"[j == n];
// }
// }
int ans = bn_search(0, 1e9+10, profit, d).first;
if(ans == -1) cout << 0 << endl;
else cout << ans << endl;
return 0;
}
详细
Subtask #1:
score: 12
Accepted
Test #1:
score: 12
Accepted
time: 72ms
memory: 5328kb
input:
100 181 1000 553730496 158361961 892706912 178296397 743382683 297380306 641674485 99624440 917350062 18856036 844421978 187895310 648680590 312745394 560991872 402321479 712754581 166489560 776432653 57402415 554268728 511597509 861517186 541462029 843246768 457630601 923371196 521104850 557772066 ...
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 35ms
memory: 3796kb
input:
100 100 1 1 1 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 100...
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 22ms
memory: 3688kb
input:
100 100 1 1 1 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 100...
output:
9999999
result:
ok single line: '9999999'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
50 98 1 294990003 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 481362725 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
1968
result:
ok single line: '1968'
Test #5:
score: 0
Accepted
time: 4ms
memory: 3544kb
input:
50 146 2 159591094 -1 152896514 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 962186931 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
12512
result:
ok single line: '12512'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
50 50 3 724315557 40661616 888500313 492213321 669530670 343751759 -1 349184557 -1 123681117 -1 416489184 -1 376740434 -1 524659730 -1 308601359 -1 544715761 -1 206108083 -1 241453594 -1 500022763 -1 65259007 -1 210716628 -1 32350566 -1 167450879 -1 397678219 -1 484826182 -1 132481950 -1 139031923 -...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 4ms
memory: 3580kb
input:
50 50 50 891479383 484772280 972520765 460897526 852794515 220696128 675355181 162826783 595520625 317178479 928536077 41783603 637233354 48683751 939337578 12210312 835648124 328095767 884417707 439843653 604057461 198149458 682206647 375826043 628570854 479841622 973619107 171111598 901599380 4192...
output:
1200008
result:
ok single line: '1200008'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
4 4 1 1 -1 -1 2 -1 17 -1 15 1 2 1 2 3 1 3 4 1 4 1 1
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 3ms
memory: 3500kb
input:
50 50 1 1 1 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 1000000000 -1 10000...
output:
19999999
result:
ok single line: '19999999'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
50 146 10 751094001 488028533 670635071 279189552 719865752 62857436 945035157 99942140 635724731 336304928 539721394 260175851 762704228 41970290 951557180 106161633 464415091 134662977 833758012 522554183 -1 30927372 -1 281363132 -1 64696223 -1 35169633 -1 426745823 -1 235500852 -1 380932326 -1 16...
output:
20025608
result:
ok single line: '20025608'
Test #11:
score: 0
Accepted
time: 3ms
memory: 3484kb
input:
50 144 5 669304181 -1 479970956 -1 167649828 -1 470258299 -1 885426197 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
65926480
result:
ok single line: '65926480'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
10 18 1 167140269 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 902165905 -1 -1 -1 -1 9 3 1 3 8 1 4 6 1 5 1 1 2 1 1 6 1 1 2 7 1 8 7 1 2 5 1 1 2 1 1 6 1 8 4 1 7 1 1 1 9 1 10 1 1 2 10 1 3 7 1 9 5 1
output:
147005127
result:
ok single line: '147005127'
Test #13:
score: 0
Accepted
time: 6ms
memory: 3640kb
input:
50 100 50 853543611 84398909 750508785 293224633 467984755 368609270 660008525 69724893 777295826 543143283 660075741 355270173 942285924 207494807 940093193 281162609 535796018 299388697 712530736 204347888 999684888 220043146 779150015 396635929 891605908 484405769 785572566 4921986 907713030 7234...
output:
0
result:
ok single line: '0'
Subtask #2:
score: 21
Accepted
Test #14:
score: 21
Accepted
time: 2ms
memory: 3548kb
input:
50 50 20 1000000000 94476 1000000000 75837 1000000000 27079 1000000000 129004 1000000000 100830 1000000000 98560 1000000000 99302 1000000000 65993 30410 1 1000000000 66183 1000000000 89148 1000000000 21236 1000000000 11935 1000000000 53895 1000000000 126490 1000000000 104741 1000000000 78615 1000000...
output:
1003
result:
ok single line: '1003'
Test #15:
score: 0
Accepted
time: 4ms
memory: 3500kb
input:
50 50 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 339508586 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
15782746
result:
ok single line: '15782746'
Test #16:
score: 0
Accepted
time: 5ms
memory: 3568kb
input:
50 50 50 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10000 10000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
203
result:
ok single line: '203'
Test #17:
score: 0
Accepted
time: 5ms
memory: 3524kb
input:
48 48 50 -1 -1 10002 10002 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
212
result:
ok single line: '212'
Test #18:
score: 0
Accepted
time: 6ms
memory: 3580kb
input:
50 50 50 662985743 94901609 899384837 65628166 673532122 180059305 627752310 127592351 824072744 87540640 507122543 377977048 635262419 187630987 838541684 187757801 577199874 274873255 694303855 184204318 853356130 175381182 520003147 69588361 734732717 178931356 807461406 173458145 548944353 44467...
output:
24700682
result:
ok single line: '24700682'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3424kb
input:
5 6 2 -1 7 -1 120 -1 -1 -1 152 1 -1 -1 -1 -1 15 -1 101 -1 -1 100 -1 1 2 1 2 3 1 3 1 1 1 4 1 4 5 1 5 1 1
output:
11
result:
ok single line: '11'
Test #20:
score: 0
Accepted
time: 4ms
memory: 3568kb
input:
50 80 10 1000000000 37352 1000000000 17646 1000000000 70743 1000000000 72743 1000000000 92712 1000000000 101408 1000000000 87555 1000000000 93907 1000000000 29236 1000000000 76657 -1 -1 -1 -1 -1 -1 -1 -1 93712 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
888
result:
ok single line: '888'
Test #21:
score: 0
Accepted
time: 6ms
memory: 3644kb
input:
50 100 50 1000000000 70830 1000000000 63070 1000000000 61439 1000000000 61975 1000000000 22624 1000000000 49915 1000000000 47462 1000000000 87935 1000000000 56993 1000000000 46192 1000000000 61181 1000000000 24487 1000000000 8489 1000000000 100547 1000000000 11972 1000000000 62570 1000000000 31811 1...
output:
1280
result:
ok single line: '1280'
Test #22:
score: 0
Accepted
time: 4ms
memory: 3548kb
input:
50 80 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 145057260 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 280991963 280991963 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 71816531 71816531 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
48692368
result:
ok single line: '48692368'
Test #23:
score: 0
Accepted
time: 4ms
memory: 3576kb
input:
50 80 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 973674914 973674914 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 296561603 -1 -1 -1 282336401 -1...
output:
33194691
result:
ok single line: '33194691'
Test #24:
score: 0
Accepted
time: 5ms
memory: 3540kb
input:
50 187 50 830841810 429573274 595571573 146280515 492250538 468812018 776848926 319177361 666252349 496736685 750060714 515499313 566368754 72927424 974159134 479439560 975472850 125615878 906298599 169893639 719670509 271733463 473128793 364199681 542408747 370312066 503590319 281153746 632823527 2...
output:
61255181
result:
ok single line: '61255181'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3520kb
input:
50 100 50 969635460 427508760 863039420 144198933 533634353 456547090 948068930 449609376 504513760 100099688 594014427 331720624 719966879 183098785 681359049 221725712 908596608 69523431 658733082 411951994 531063785 530194941 517539642 514023120 878107325 175669958 531003748 120509045 769867951 4...
output:
48262703
result:
ok single line: '48262703'
Test #26:
score: 0
Accepted
time: 4ms
memory: 3596kb
input:
50 2450 1 873538879 77537323 981428881 443257378 706113412 86188501 551816872 136407163 775854228 529874644 833357312 164234816 789796900 161224551 782938565 351773996 524273413 221302707 670302513 194826791 930267291 92690365 465264422 198885657 837453031 461954416 892265285 142180433 613974685 497...
output:
35859005
result:
ok single line: '35859005'
Test #27:
score: 0
Accepted
time: 4ms
memory: 3616kb
input:
50 200 21 643668133 390520483 658543702 388943069 605637169 338250245 944977442 19085220 744455499 469334973 716186529 376723863 822608487 261409511 835985600 194242073 849987225 307993073 671141152 436231948 688823523 216262977 460579236 402881121 785133016 549171256 601998630 17008520 626607192 27...
output:
49223640
result:
ok single line: '49223640'
Test #28:
score: 0
Accepted
time: 5ms
memory: 3564kb
input:
50 2450 50 502077015 469045625 489968527 452674638 505803345 496827751 538648562 465058738 545376062 536770029 515365394 476671277 485590735 474944209 516276629 453636182 477817475 460003764 480168383 475732557 458054538 455560310 537744626 499113397 534144232 466826235 549153755 483115613 526201164...
output:
78757153
result:
ok single line: '78757153'
Test #29:
score: 0
Accepted
time: 4ms
memory: 3536kb
input:
50 96 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 888211806 888211806 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
46463592
result:
ok single line: '46463592'
Test #30:
score: 0
Accepted
time: 5ms
memory: 3524kb
input:
50 50 50 55859 55859 123482 123482 79889 79889 41061 41061 49131 49131 43257 43257 56425 56425 65649 65649 74722 74722 51980 51980 59441 59441 16955 16955 45044 45044 113078 113078 75246 75246 55050 55050 102102 102102 73125 73125 86088 86088 23312 23312 98013 98013 67756 67756 72788 72788 127435 12...
output:
1167
result:
ok single line: '1167'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
4 4 3 1 1 5 5 6 6 2 2 8 8 7 7 6 6 9 9 8 8 2 2 7 7 1 1 1 2 1 2 3 1 3 4 1 4 1 1
output:
3
result:
ok single line: '3'
Test #32:
score: 0
Accepted
time: 5ms
memory: 3528kb
input:
50 50 50 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1...
output:
999999999
result:
ok single line: '999999999'
Test #33:
score: 0
Accepted
time: 5ms
memory: 3536kb
input:
50 191 50 681638163 681638163 343296899 343296899 455415345 455415345 612427809 612427809 520683747 520683747 476224943 476224943 396014800 396014800 570649011 570649011 606265889 606265889 446213315 446213315 446918088 446918088 413684488 413684488 431956363 431956363 331088687 331088687 424310265 ...
output:
406615161
result:
ok single line: '406615161'
Test #34:
score: 0
Accepted
time: 5ms
memory: 3528kb
input:
50 100 50 545869997 545869997 377928992 377928992 450769023 450769023 454866452 454866452 613093501 613093501 477393640 477393640 489106706 489106706 399547137 399547137 601629557 601629557 520007927 520007927 358561182 358561182 593593592 593593592 433980627 433980627 358439100 358439100 521143188 ...
output:
399192910
result:
ok single line: '399192910'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
50 2450 2 662981629 662981629 429186593 429186593 398152552 398152552 338846288 338846288 345165906 345165906 400176481 400176481 349476026 349476026 579837991 579837991 449954858 449954858 455002792 455002792 408717841 408717841 555085433 555085433 508941564 508941564 593569047 593569047 479450019 ...
output:
323385804
result:
ok single line: '323385804'
Test #36:
score: 0
Accepted
time: 4ms
memory: 3568kb
input:
50 80 3 551325411 551325411 464192800 464192800 480332644 480332644 347097460 347097460 734638978 734638978 584879997 584879997 284204584 284204584 569594556 569594556 684653270 684653270 671544567 671544567 493774054 493774054 536089517 536089517 255657036 255657036 574572675 574572675 494316360 49...
output:
223340615
result:
ok single line: '223340615'
Subtask #3:
score: 33
Accepted
Test #37:
score: 33
Accepted
time: 102ms
memory: 5252kb
input:
100 243 1000 969713863 380451398 977287381 546839551 578242281 267067963 834635238 316438277 806980243 189648353 779415475 453867771 741678190 352485450 473763928 190177433 687118672 377243148 644333594 197290749 949048287 436673078 690006797 180711316 714366028 387342721 980055654 198167471 8873988...
output:
28
result:
ok single line: '28'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
5 7 4 727218133 319808016 451811473 341827334 983666612 208956608 712124347 20325770 625539547 511168571 950094471 396282690 649119245 412489786 504515934 498965733 955685647 120970424 900386157 487638774 666900039 254430876 841869836 23162184 670731166 282497058 791738936 425566820 916482877 602671...
output:
8
result:
ok single line: '8'
Test #39:
score: 0
Accepted
time: 7ms
memory: 3608kb
input:
50 100 100 738055508 380547266 466519731 321379362 627164749 501738148 790388363 534474035 594031599 289323442 585921101 400847039 988432406 326676078 973287243 480408179 677194803 254403874 960518968 523054718 490930760 258858830 532158736 498097146 823424101 17095805 770242306 523332445 830717940 ...
output:
138919
result:
ok single line: '138919'
Test #40:
score: 0
Accepted
time: 3ms
memory: 3620kb
input:
50 100 100 714420219 664420219 670988077 620988077 749695455 699695455 567602634 546701549 630315751 580315751 548562478 510475293 734437437 684437437 517242293 467242293 712844065 662844065 530370481 480370481 584518044 534518044 780621679 730621679 542815120 533903899 599496563 549496563 709776870...
output:
2773
result:
ok single line: '2773'
Test #41:
score: 0
Accepted
time: 13ms
memory: 3648kb
input:
50 80 100 613124154 298784098 537389012 279713205 499689681 471314836 886103757 60087694 845068143 368855914 648389008 300242966 646640622 221676660 866330078 514509030 604069994 416492438 611394991 453739552 732469971 524033149 694292198 5271026 573810521 471002300 531489460 212864274 881123884 266...
output:
49797
result:
ok single line: '49797'
Test #42:
score: 0
Accepted
time: 98ms
memory: 5380kb
input:
100 9900 1000 986355298 343941451 748009505 157768582 549897631 353675832 784259651 71183802 455272137 239882644 688026841 125591164 861653505 535779783 761535420 360625660 485161701 275682287 548652543 525094271 577374254 540601357 586092427 379551990 490170545 79852082 804653532 513745338 55248752...
output:
2478
result:
ok single line: '2478'
Test #43:
score: 0
Accepted
time: 98ms
memory: 5388kb
input:
100 9900 1000 727914573 352681283 745159911 478069159 524736757 267716315 554533162 49659853 704220141 272866726 878406576 349556214 606558787 31608223 752128450 136602787 645580703 226343143 981500098 238380602 863321669 443495332 937077574 118463117 609547732 88002197 787077169 405900536 776842331...
output:
1330867
result:
ok single line: '1330867'
Test #44:
score: 0
Accepted
time: 35ms
memory: 3848kb
input:
100 100 100 289207 289207 384956 384956 229259 229259 546415 546415 171739 171739 282850 282850 221135 221135 16583 16583 370773 370773 119341 119341 426085 426085 440159 440159 253180 253180 529005 529005 428704 428704 211778 211778 309906 309906 325591 325591 156929 156929 288408 288408 422082 422...
output:
830
result:
ok single line: '830'
Test #45:
score: 0
Accepted
time: 89ms
memory: 5100kb
input:
100 500 900 370608755 370608755 394298561 394298561 477985939 477985939 312239957 312239957 742647608 742647608 346481586 346481586 535875402 535875402 711205883 711205883 538460115 538460115 399559367 399559367 716685729 716685729 631088306 631088306 420575105 420575105 418270029 418270029 45272598...
output:
2936107
result:
ok single line: '2936107'
Test #46:
score: 0
Accepted
time: 33ms
memory: 3788kb
input:
100 563 40 490783053 490783053 500616737 500616737 610816964 610816964 630654725 630654725 605493528 605493528 374238654 374238654 452823555 452823555 519705766 519705766 537548608 537548608 447518535 447518535 524316798 524316798 551017738 551017738 662639933 662639933 574991144 574991144 505436345...
output:
2420209
result:
ok single line: '2420209'
Test #47:
score: 0
Accepted
time: 41ms
memory: 3876kb
input:
100 100 100 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
100
result:
ok single line: '100'
Test #48:
score: 0
Accepted
time: 30ms
memory: 3884kb
input:
100 100 100 1 1 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
999999999
result:
ok single line: '999999999'
Test #49:
score: 0
Accepted
time: 27ms
memory: 3820kb
input:
100 596 40 358458945 358458945 331034157 331034157 349074033 349074033 344044690 344044690 485167401 485167401 734094465 734094465 530915559 530915559 589250413 589250413 256795508 256795508 489343536 489343536 534470289 534470289 267233079 267233079 482426953 482426953 626623725 626623725 648411549...
output:
2394068
result:
ok single line: '2394068'
Subtask #4:
score: 34
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #50:
score: 34
Accepted
time: 28ms
memory: 3712kb
input:
100 100 20 1000000000 20107340 1000000000 84690988 1000000000 51566432 1000000000 19246854 1000000000 74298508 1000000000 67607916 1000000000 13482381 1000000000 66690855 1000000000 21060231 1000000000 58257449 1000000000 94247765 1000000000 42030918 1000000000 54399988 1000000000 31460631 100000000...
output:
999
result:
ok single line: '999'
Test #51:
score: 0
Accepted
time: 35ms
memory: 3872kb
input:
100 100 100 1000000000 30513031 1000000000 14357871 1000000000 48546647 1000000000 50402761 1000000000 13373766 1000000000 977044 1000000000 5757773 1000000000 94167615 1000000000 77228809 1000000000 45580007 1000000000 38109976 1000000000 31543094 1000000000 10468167 1000000000 66725618 1000000000 ...
output:
1000
result:
ok single line: '1000'
Test #52:
score: 0
Accepted
time: 48ms
memory: 4940kb
input:
100 100 800 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 172290281 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
9054
result:
ok single line: '9054'
Test #53:
score: 0
Accepted
time: 35ms
memory: 3948kb
input:
100 100 100 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
10075
result:
ok single line: '10075'
Test #54:
score: 0
Accepted
time: 35ms
memory: 3924kb
input:
100 900 102 -1 -1 -1 -1 998132565 998132565 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
10077
result:
ok single line: '10077'
Test #55:
score: 0
Accepted
time: 32ms
memory: 3928kb
input:
100 910 102 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
10089
result:
ok single line: '10089'
Test #56:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
8 9 3 -1 80 -1 -1 -1 -1 -1 -1 200 -1 -1 -1 -1 -1 -1 800 -1 -1 -1 -1 -1 -1 1000 -1 -1 -1 -1 -1 -1 6200 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 1 2 10 2 3 10 3 8 10 1 4 100 4 5 100 5 8 100 8 6 10 6 7 10 7 1 10
output:
15
result:
ok single line: '15'
Test #57:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
8 9 3 -1 80 -1 -1 -1 -1 -1 -1 200 -1 -1 -1 -1 -1 -1 800 -1 -1 -1 -1 -1 -1 1000 -1 -1 -1 -1 -1 -1 6200 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 -1 -1 -1 -1 -1 1 2 10 2 3 10 3 8 10 1 4 100 4 5 100 5 8 100 8 6 1 6 7 1 7 1 1
output:
20
result:
ok single line: '20'
Test #58:
score: 0
Accepted
time: 30ms
memory: 3824kb
input:
100 1000 10 1000000000 16802079 1000000000 24761954 1000000000 16382558 1000000000 24715365 1000000000 17666000 1000000000 16919190 1000000000 16856786 1000000000 17073373 1000000000 25004590 1000000000 24850075 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
7450
result:
ok single line: '7450'
Test #59:
score: 0
Accepted
time: 38ms
memory: 3828kb
input:
100 9900 10 1000000000 8459244 1000000000 8473171 1000000000 8486152 1000000000 9037969 1000000000 8240240 1000000000 8662280 1000000000 8830053 1000000000 8586515 1000000000 8559494 1000000000 8779064 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
67
result:
ok single line: '67'
Test #60:
score: 0
Accepted
time: 34ms
memory: 3740kb
input:
100 200 40 1000000000 40666 1000000000 6755 1000000000 87003 1000000000 5374 1000000000 33472 1000000000 100001 1000000000 61451 1000000000 47511 1000000000 38436 1000000000 81927 1000000000 56456 1000000000 78948 1000000000 76056 1000000000 52490 1000000000 20676 1000000000 86824 1000000000 91804 1...
output:
9
result:
ok single line: '9'
Test #61:
score: 0
Accepted
time: 26ms
memory: 3724kb
input:
100 250 30 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 792819644 792819644 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
96587
result:
ok single line: '96587'
Test #62:
score: 0
Accepted
time: 32ms
memory: 3708kb
input:
100 1000 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
output:
111863
result:
ok single line: '111863'
Extra Test:
score: 0
Extra Test Passed