QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#44750 | #2021. 有源汇有上下界最小费用最大流(随机数据) | Remakee# | AC ✓ | 1648ms | 4112kb | C++14 | 3.2kb | 2022-08-21 14:44:58 | 2022-08-21 14:45:01 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
template <typename T> bool inline chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
x = 0; int f = 1; char s = getchar();
while (s > '9' || s < '0') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + s - '0', s = getchar();
x *= f;
}
const int N = 1e3 + 5, M = 6e3 + 5;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int n, m, s, t;
LL h[N], d[N];
struct E{
int next, v, w, c;
} e[M << 1];
int head[N], numE = 1;
void add(int u, int v, int w, int c) {
e[++numE] = (E) { head[u], v, w , c};
head[u] = numE;
}
void addE(int u, int v, int w, int c) {
add(u, v, w, c), add(v, u, 0, -c);
}
int pre[N];
LL incf[N];
void upd() {
int x = t;
while (x != s) {
int i = pre[x];
e[i].w -= incf[t], e[i ^ 1].w += incf[t];
x = e[i ^ 1].v;
}
}
typedef pair<LL, int> PLI;
priority_queue<PLI, vector<PLI>, greater<PLI> > q;
bool vis[N];
bool dij() {
memset(d, 0x3f, sizeof d);
memset(vis, 0, sizeof vis);
d[s] = 0;
q.push(mp(0, s));
incf[s] = INF;
while (!q.empty()) {
int u = q.top().se; q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i ; i = e[i].next) {
int v = e[i].v;
if (e[i].w && chkMin(d[v], d[u] + h[u] + e[i].c - h[v])) {
q.push(mp(d[v], v));
incf[v] = min(incf[u], (LL)e[i].w);
pre[v] = i;
}
}
}
return d[t] != INF;
}
int Q[N];
void spfa() {
memset(h, 0x3f, sizeof h);
int hh = 0, tt = 1;
Q[0] = s; h[s] = 0;
while (hh != tt) {
int u = Q[hh++];
if (hh == N) hh = 0;
vis[u] = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w) {
if (h[u] + e[i].c < h[v]) {
h[v] = h[u] + e[i].c;
if (!vis[v]) {
vis[v] = 1;
Q[tt++] = v;
if (tt == N) tt = 0;
}
}
}
}
}
}
int a[N];
LL ans = 0;
void addEdge(int u, int v, int L, int R, int c) {
R -= L;
ans += (LL)L * c;
a[v] += L, a[u] -= L;
addE(u, v, R, c);
}
int main() {
read(n), read(m); int S, T; read(S), read(T);
s = n + 1, t = n + 2;
for (int i = 1; i <= m; i++) {
int u, v, l, r, c; read(u), read(v), read(l), read(r), read(c);
if (c >= 0) addEdge(u, v, l, r, c);
else {
a[v] += r, a[u] -= r;
ans += 1ll * c * r;
addE(v, u, r - l, -c);
}
}
LL sm = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > 0) addE(s, i, a[i], 0), sm += a[i];
else addE(i, t, -a[i], 0);
}
addE(T, S, 1e9, 0);
//spfa();
while (dij()) {
for (int i = 1; i <= n + 2; i++) h[i] += d[i];
upd();
ans += h[t] * incf[t];
sm -= incf[t];
}
if (sm) {
puts("-1");
return 0;
}
LL fl = 0;
fl = e[numE].w;
e[numE].w = e[numE - 1].w = 0;
s = S, t = T;
spfa();
while (dij()) {
for (int i = 1; i <= n + 2; i++) h[i] += d[i];
ans += h[t] * incf[t];
fl += incf[t];
upd();
}
printf("%lld %lld\n", fl, ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3720kb
input:
3 3 1 3 1 2 0 6 0 2 3 1 1000 4 2 3 0 1000 3
output:
6 19
result:
ok 2 number(s): "6 19"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
5 6 2 4 2 1 1 6 4 2 3 0 5 1 1 3 2 8 2 3 4 1 7 1 3 5 0 4 1 5 4 1 5 2
output:
11 60
result:
ok 2 number(s): "11 60"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
3 1 1 3 2 3 1 100 -100
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
6 20 3 2 2 6 31 62 -14 6 5 18 75 -5 3 4 19 46 -94 3 6 6 47 -84 4 5 1 100 38 3 4 1 33 -64 1 2 31 59 92 6 2 1 74 -17 3 4 40 40 0 6 3 18 95 67 3 1 22 99 -87 5 4 19 33 -59 3 5 24 74 13 5 2 19 83 22 2 1 3 10 -81 3 1 6 76 -21 3 5 12 46 60 5 3 17 55 92 2 4 1 7 42 4 2 79 99 -3
output:
248 -6071
result:
ok 2 number(s): "248 -6071"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
6 20 5 4 5 2 1624 533269 -139880 2 4 0 15565 24058 1 3 0 0 0 2 5 2565 220226 604019 3 4 1165 51064 264995 2 6 0 84605 801197 1 5 0 375912 438852 4 6 2025 677043 359279 4 3 2078 15429 -606365 5 4 3253 669243 288789 3 4 2991 988592 -599399 5 6 1159 792735 -727904 5 2 941 159641 90003 5 4 4264 987824 5...
output:
3268997 -609038394670
result:
ok 2 number(s): "3268997 -609038394670"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
6 20 3 4 4 2 70379 363446 -216271 3 1 40731 817362 -610850 5 3 45928 603804 335372 4 1 14839 889225 279553 1 4 111451 645417 -660802 3 1 30534 887172 -788179 5 4 9595 15783 559723 5 4 19320 892283 -997184 6 1 13966 926157 -279930 2 6 55766 969481 923720 2 1 1626 793658 587430 3 4 16341 717826 -86874...
output:
2372477 -1008282590271
result:
ok 2 number(s): "2372477 -1008282590271"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
6 20 2 6 3 6 57096 162636 663483 6 3 12879 401950 150875 4 2 55557 991364 274301 5 3 61117 989768 675838 3 5 55211 396391 -748348 6 5 17586 268092 -668494 3 1 70661 347360 -227828 1 5 77878 599932 864205 4 2 13723 426224 -496803 4 1 0 909998 -272175 2 4 69280 512330 -751788 6 5 35697 973744 -72290 5...
output:
1434247 -19122258462
result:
ok 2 number(s): "1434247 -19122258462"
Test #8:
score: 0
Accepted
time: 6ms
memory: 3820kb
input:
50 500 15 26 5 39 0 212962 -400202 39 33 749 159440 617413 43 34 819 997092 825049 34 48 1534 318958 -144695 11 37 0 983399 -329393 19 33 0 843486 988506 32 45 1334 729326 -938178 37 9 963 626078 349608 34 42 0 243498 -20646 11 17 1011 945863 -627218 7 32 0 756672 920090 8 26 1776 807376 -455829 13 ...
output:
13894271 -34225425128509
result:
ok 2 number(s): "13894271 -34225425128509"
Test #9:
score: 0
Accepted
time: 11ms
memory: 3896kb
input:
50 1000 29 12 9 34 782 375064 127907 4 40 2085 764570 -90435 43 8 1460 166821 4596 11 35 826 470840 555882 16 46 0 812869 937386 1 12 405 670247 125943 36 38 0 85327 911102 29 33 558 81202 -394257 38 17 0 939407 175104 31 34 1360 547503 180904 37 27 0 536387 -87498 23 19 0 744774 -83406 12 34 0 6048...
output:
16141906 -91411803962527
result:
ok 2 number(s): "16141906 -91411803962527"
Test #10:
score: 0
Accepted
time: 3ms
memory: 3800kb
input:
50 500 41 39 25 32 10892 96360 200856 13 24 916 878509 701236 41 38 2498 56477 -277527 5 34 4978 182292 740911 18 10 6455 733105 989389 2 49 3105 72791 354971 23 34 3337 676388 365240 28 31 3871 101717 -460592 27 3 3076 536700 264447 41 43 3299 963677 -239011 24 33 3544 213942 -760051 18 39 2809 221...
output:
15723908 -35056194400006
result:
ok 2 number(s): "15723908 -35056194400006"
Test #11:
score: 0
Accepted
time: 8ms
memory: 3756kb
input:
50 1000 23 30 37 35 903 256723 827278 46 32 1509 53354 -600251 23 27 782 528624 907754 14 10 433 725919 957890 39 7 221 59498 -722846 2 7 1364 868063 815478 15 17 2289 571446 -257636 26 6 2705 960604 -465141 19 31 1089 902070 -969714 21 17 2552 651978 867173 24 2 1066 609780 -820634 20 15 1713 99315...
output:
20935812 -101080647346631
result:
ok 2 number(s): "20935812 -101080647346631"
Test #12:
score: 0
Accepted
time: 6ms
memory: 3808kb
input:
50 500 11 3 39 5 24154 413052 205168 2 33 9529 541066 424543 34 3 16649 794388 197716 34 23 21794 588796 883090 24 39 28843 143048 -199922 4 45 14611 978980 -517850 18 33 49112 584887 -895326 9 8 26436 637602 968040 46 31 31657 220325 -42763 45 7 15871 559299 702791 5 4 49864 83225 -624236 14 13 218...
output:
13665538 -38120035984842
result:
ok 2 number(s): "13665538 -38120035984842"
Test #13:
score: 0
Accepted
time: 10ms
memory: 3756kb
input:
50 1000 48 28 49 3 8973 992305 456075 19 28 6274 999944 944105 42 31 18444 84155 927380 20 35 23136 260274 878320 34 20 13729 548312 -909235 44 4 13089 286792 429914 49 33 7793 348091 66713 8 16 12852 142118 888601 47 24 15223 53363 -416012 1 48 15878 138026 255612 36 37 13937 731566 966874 22 34 16...
output:
16133026 -98703594100601
result:
ok 2 number(s): "16133026 -98703594100601"
Test #14:
score: 0
Accepted
time: 3ms
memory: 3736kb
input:
50 500 15 8 49 48 40983 609788 -37099 11 35 57810 653761 892772 34 47 15798 999787 464642 22 13 85779 860378 839353 17 21 32282 898304 -627263 49 20 34703 469070 -672512 25 33 73215 632814 233722 6 8 101071 363704 587018 21 36 107035 589881 -418601 14 16 82595 573207 -585063 41 20 87473 755950 98771...
output:
17121568 -37734255010971
result:
ok 2 number(s): "17121568 -37734255010971"
Test #15:
score: 0
Accepted
time: 9ms
memory: 3736kb
input:
50 1000 2 41 9 28 46576 220919 426564 21 25 35782 999199 -255105 13 31 22103 60319 -970608 20 42 69794 788521 -653078 19 7 58425 318051 -358974 19 11 49686 527789 791115 5 10 44593 167664 -784621 30 15 24518 467971 797692 6 20 50096 735904 -229790 49 20 36221 64498 -400378 29 10 20624 32279 -844830 ...
output:
23605188 -101167595426821
result:
ok 2 number(s): "23605188 -101167595426821"
Test #16:
score: 0
Accepted
time: 639ms
memory: 4060kb
input:
500 5000 281 370 104 141 24928 399165 318883 465 458 13354 998793 -484579 360 479 15492 714564 500923 14 10 21965 962142 986486 330 429 6839 119285 984012 56 305 6479 100934 -826957 97 151 7627 619199 546926 102 224 17467 506542 -555847 482 16 3106 131352 45305 316 252 36357 906300 868577 11 352 183...
output:
34847519 -444887888307815
result:
ok 2 number(s): "34847519 -444887888307815"
Test #17:
score: 0
Accepted
time: 67ms
memory: 3772kb
input:
1000 1000 329 501 642 456 0 303370 745624 404 687 0 952485 -488473 148 172 0 61082 -973829 217 61 0 676342 -927881 927 935 0 876728 -412472 918 781 0 425479 -136952 118 652 0 559605 -719695 823 902 0 361443 694308 676 331 0 248417 -759727 922 359 0 806571 667500 319 702 0 513441 -768840 85 742 0 962...
output:
0 25391368368
result:
ok 2 number(s): "0 25391368368"
Test #18:
score: 0
Accepted
time: 64ms
memory: 3880kb
input:
1000 1000 68 678 177 442 0 174955 -605128 901 797 0 889103 -803112 430 49 0 560456 999218 660 263 0 589544 -984111 666 227 0 595986 6222 163 678 0 487372 -762185 932 463 0 142928 -756402 513 374 0 86019 158660 980 222 0 97407 -817946 769 412 0 278390 -98326 632 272 0 4286 -535349 157 437 0 19750 375...
output:
49350 -50607990524
result:
ok 2 number(s): "49350 -50607990524"
Test #19:
score: 0
Accepted
time: 270ms
memory: 3908kb
input:
1000 2000 289 539 336 369 6499 107222 319238 616 105 12063 655949 991994 953 228 15875 324902 657386 913 523 0 716138 -197 676 726 0 579348 889086 707 996 0 554031 -913100 307 201 0 52022 -314985 452 666 15028 81970 -418183 175 539 35105 363649 -5018 214 785 0 558699 -337890 511 323 4752 355738 9226...
output:
5999179 -26019371993017
result:
ok 2 number(s): "5999179 -26019371993017"
Test #20:
score: 0
Accepted
time: 552ms
memory: 3956kb
input:
1000 3000 806 399 975 881 7262 72158 687818 50 838 2575 489162 592083 146 752 0 729780 886803 448 853 0 467811 308183 942 600 39644 766436 -275212 71 241 33009 604439 505199 279 595 3605 567878 62565 559 648 32675 819733 -114862 346 159 4559 9698 108900 69 849 5798 583360 -84177 198 540 14175 19515 ...
output:
8698539 -106302791961013
result:
ok 2 number(s): "8698539 -106302791961013"
Test #21:
score: 0
Accepted
time: 1124ms
memory: 4048kb
input:
1000 5000 248 17 798 971 5562 166715 877758 514 944 14428 836703 -615339 311 692 5260 40829 916168 181 714 1594 823163 18587 847 870 19271 827541 -517441 946 310 4699 460521 -737871 435 570 5367 274153 -186395 312 720 11335 974940 -968280 946 425 4263 808924 -690207 661 872 9274 116440 611161 855 11...
output:
13538466 -348967770000544
result:
ok 2 number(s): "13538466 -348967770000544"
Test #22:
score: 0
Accepted
time: 1249ms
memory: 3968kb
input:
1000 5000 335 892 81 448 34513 444814 716767 740 544 44777 949704 274318 190 722 23066 101746 622944 946 454 363 35002 360283 222 626 4464 693792 -709886 220 173 22835 304823 -612622 441 816 13311 468419 -456262 390 376 16924 721511 834972 14 107 11597 91042 130955 872 311 1882 790437 237497 264 473...
output:
29282723 -326686986015291
result:
ok 2 number(s): "29282723 -326686986015291"
Test #23:
score: 0
Accepted
time: 1280ms
memory: 3960kb
input:
1000 5000 331 338 431 204 14386 771648 740204 281 19 43 74222 362047 702 690 3290 779701 201867 779 34 6703 670699 74531 533 757 12642 36559 -936215 76 953 36889 343239 -623625 909 168 10496 768983 -114706 519 958 15097 73213 -993240 387 374 4856 85052 -840616 879 338 22002 763083 18933 964 543 7060...
output:
28016777 -329477934757237
result:
ok 2 number(s): "28016777 -329477934757237"
Test #24:
score: 0
Accepted
time: 1355ms
memory: 4012kb
input:
1000 5000 85 216 718 237 5977 392706 -485547 808 72 0 360740 990712 815 509 13783 933495 913113 224 479 5804 858119 -22296 475 531 1490 348416 -852046 876 807 5415 275592 -204849 114 991 16506 513922 90180 972 956 13392 842463 982593 861 206 7442 995725 603009 813 210 12012 735286 497228 675 216 0 6...
output:
33304587 -310312433309877
result:
ok 2 number(s): "33304587 -310312433309877"
Test #25:
score: 0
Accepted
time: 1294ms
memory: 3964kb
input:
1000 5000 233 373 900 671 0 424558 399591 801 565 7542 265469 780149 289 688 10566 545513 -186326 803 627 1038 981105 -750051 591 797 11 917205 645607 971 934 18345 456747 180843 931 648 24749 665297 637396 82 335 10523 594448 -229124 166 674 10013 260824 -834049 194 498 12823 213968 923260 323 367 ...
output:
33263232 -321943865677110
result:
ok 2 number(s): "33263232 -321943865677110"
Test #26:
score: 0
Accepted
time: 1328ms
memory: 4016kb
input:
1000 5000 364 679 241 79 4898 560222 -902209 940 907 8447 354220 -360989 619 412 40326 571760 366130 910 745 2292 25769 326643 91 12 4971 127973 742938 322 204 31182 426801 305633 506 244 13832 769833 -974527 300 324 14592 834409 -270222 15 425 0 768111 663648 10 207 24491 920830 466912 17 693 17579...
output:
48646091 -275455005459403
result:
ok 2 number(s): "48646091 -275455005459403"
Test #27:
score: 0
Accepted
time: 1566ms
memory: 3972kb
input:
1000 5000 933 228 206 228 15327 275686 985028 882 573 313 948888 -815623 544 9 1436 769936 233130 885 228 8146 653541 997950 749 902 22111 344680 798769 453 666 60080 426599 896661 78 438 58289 81973 989235 315 228 23039 177059 -496477 580 577 44756 245320 -28988 416 842 10042 981717 839733 552 492 ...
output:
107177048 -292368356606276
result:
ok 2 number(s): "107177048 -292368356606276"
Test #28:
score: 0
Accepted
time: 1635ms
memory: 3984kb
input:
1000 5000 206 584 155 809 0 300382 -474253 155 994 79 70848 120744 476 246 23401 92938 -915430 452 808 22095 278707 558893 539 982 57354 885170 -761257 170 584 12058 814511 -145493 104 723 14014 770567 -899978 783 584 11320 744106 -496552 173 979 17009 513277 429382 359 568 29028 877760 970368 914 1...
output:
148850020 -223299573015245
result:
ok 2 number(s): "148850020 -223299573015245"
Test #29:
score: 0
Accepted
time: 1495ms
memory: 4052kb
input:
1000 5000 140 675 196 282 9182 828209 -503719 93 445 0 140283 -135183 596 123 8599 815365 816974 135 264 5622 25495 -766990 351 721 7466 106977 -155302 865 675 11515 204511 -97156 388 693 23236 799923 -557331 129 809 13316 466181 -836445 722 546 14116 449229 773535 140 659 19546 192249 -336816 433 5...
output:
145492839 -247490323782779
result:
ok 2 number(s): "145492839 -247490323782779"
Test #30:
score: 0
Accepted
time: 1475ms
memory: 4008kb
input:
1000 5000 931 272 50 873 7609 47533 -541139 4 272 14101 473798 -234092 931 690 13993 721488 186151 162 269 16957 389284 -393731 729 733 34902 83042 -724763 134 272 11923 999883 -726588 364 391 1650 85571 597008 556 16 1421 791030 -65237 549 272 4611 826224 -239936 748 967 2393 330209 -635818 464 909...
output:
144621615 -255096018217124
result:
ok 2 number(s): "144621615 -255096018217124"
Test #31:
score: 0
Accepted
time: 1600ms
memory: 3956kb
input:
1000 5000 739 467 309 832 2966 593332 973245 330 792 0 986911 -757580 625 467 7052 987457 -240020 537 436 0 762179 -286018 753 181 16702 980108 -27682 488 139 0 787274 -797812 733 725 28352 471108 -507002 780 58 2719 508351 -62601 122 465 1878 490135 -499442 366 969 7733 785035 -864344 504 859 0 346...
output:
151722353 -238428050831473
result:
ok 2 number(s): "151722353 -238428050831473"
Test #32:
score: 0
Accepted
time: 1462ms
memory: 4016kb
input:
1000 5000 547 788 336 623 11955 15897 -330749 401 57 34699 307352 468156 547 567 10789 889434 -831117 547 900 15607 487643 -498536 739 702 24600 154886 218882 327 942 27457 999628 841224 225 788 14223 893439 283724 106 996 5028 359069 901494 201 723 7324 571597 792922 623 775 18907 978410 314595 818...
output:
143626839 -212170251457291
result:
ok 2 number(s): "143626839 -212170251457291"
Test #33:
score: 0
Accepted
time: 1616ms
memory: 4100kb
input:
1000 5000 109 613 569 53 7224 159873 -175897 472 785 2950 75217 -296263 786 919 42901 274729 550899 399 494 2541 391513 -86935 118 838 3815 429821 308082 713 896 8472 960557 -378401 264 892 3174 535220 -673876 7 623 15968 942856 67725 956 298 13021 502212 -678713 421 89 6504 256909 807311 250 196 14...
output:
144036529 -240215991129164
result:
ok 2 number(s): "144036529 -240215991129164"
Test #34:
score: 0
Accepted
time: 1612ms
memory: 4020kb
input:
1000 5000 391 698 242 698 23398 524160 -2875 115 634 10453 571042 622631 675 156 9639 797698 822771 618 43 657 371060 -180346 134 627 26210 841601 280491 141 35 8219 484375 512 349 698 6895 126675 544310 259 350 2711 379576 799953 886 773 11125 367356 -289414 652 783 16216 795765 -266269 511 112 217...
output:
150199210 -230912175333369
result:
ok 2 number(s): "150199210 -230912175333369"
Test #35:
score: 0
Accepted
time: 1556ms
memory: 4008kb
input:
1000 5000 536 489 438 423 28858 606033 -161657 573 546 7472 934736 599822 567 188 9740 463001 457328 41 729 6807 933755 790788 29 724 0 754170 952168 163 489 3491 505399 725339 80 648 3870 74788 311827 536 622 9034 141507 554191 841 40 2119 6802 -95457 847 492 12769 390865 -380032 536 22 11076 20817...
output:
228212746 -191757425672435
result:
ok 2 number(s): "228212746 -191757425672435"
Test #36:
score: 0
Accepted
time: 1573ms
memory: 3944kb
input:
1000 5000 741 397 493 397 13451 346424 -561315 198 756 8598 735377 -754855 667 882 6228 9867 -335027 339 476 0 428636 -28242 597 68 3593 733789 735118 257 215 6545 761499 -955668 222 822 11030 599815 -379034 371 397 2706 808032 -7987 76 883 7692 826349 313053 271 397 4621 220057 487106 825 76 7478 1...
output:
144499952 -242630820111524
result:
ok 2 number(s): "144499952 -242630820111524"
Test #37:
score: 0
Accepted
time: 851ms
memory: 3852kb
input:
1000 5000 152 556 9 341 3771 355355 -855078 570 823 2987 341744 149967 169 491 49218 181978 -448601 390 528 13118 782248 213613 336 805 7858 132880 -801241 848 301 23568 482253 400317 189 904 3771 463726 376912 406 796 41424 270963 -152461 633 669 11289 135169 299609 480 386 8405 243959 328569 815 4...
output:
-1
result:
ok 1 number(s): "-1"
Test #38:
score: 0
Accepted
time: 854ms
memory: 3880kb
input:
1000 5000 289 525 11 295 17308 401605 -681085 466 687 22781 692572 -783748 956 17 12765 310639 221912 375 671 11746 748129 -272468 309 829 20303 869617 -860006 150 374 6565 71633 283208 166 650 60069 833189 -662572 246 93 2968 118416 -92332 915 525 15887 112847 829500 220 648 8676 98139 -19631 763 1...
output:
-1
result:
ok 1 number(s): "-1"
Test #39:
score: 0
Accepted
time: 1648ms
memory: 4008kb
input:
1000 5000 254 92 944 522 16698 849881 -149801 875 92 12069 49550 -606547 492 823 5541 373513 -386719 980 788 17283 986977 676479 271 493 1870 683452 751918 159 882 27525 305257 779710 988 868 6990 634950 343507 483 217 8603 999987 -87701 767 568 5295 379759 598420 671 189 6115 701694 -512886 972 904...
output:
239603483 -158694085808920
result:
ok 2 number(s): "239603483 -158694085808920"
Test #40:
score: 0
Accepted
time: 1623ms
memory: 4060kb
input:
1000 5000 534 246 711 701 0 630175 124080 123 807 16501 838328 369705 200 796 22459 755283 854608 654 258 9342 482939 160862 962 340 15165 672606 922533 155 731 22085 933465 903178 338 597 12071 247849 -482139 388 933 1757 716322 -866429 19 543 998 317542 -696521 457 246 13566 45552 -860363 534 958 ...
output:
137826221 -246223007039699
result:
ok 2 number(s): "137826221 -246223007039699"
Test #41:
score: 0
Accepted
time: 1439ms
memory: 4096kb
input:
1000 5000 323 190 351 34 6039 703904 -241657 33 978 19118 677300 793269 417 5 17497 748233 -425177 202 802 18705 976056 714523 794 694 5076 368922 592561 472 688 17913 641137 589194 425 784 18528 355757 802646 710 467 18116 416644 792572 87 116 6237 564281 752619 857 872 3799 9213 915257 419 946 203...
output:
125711894 -263417304091920
result:
ok 2 number(s): "125711894 -263417304091920"
Test #42:
score: 0
Accepted
time: 1432ms
memory: 4112kb
input:
1000 5000 247 561 129 767 15082 994677 -487040 524 986 8752 916746 -4624 226 142 8986 692155 791292 801 639 4385 514261 272261 417 79 4553 981494 458671 541 803 4670 296052 -933521 310 494 1382 833336 -917169 509 948 3404 848217 781732 315 290 22031 625173 -682118 641 101 1664 722700 -1819 809 508 9...
output:
129446151 -279645239058344
result:
ok 2 number(s): "129446151 -279645239058344"
Test #43:
score: 0
Accepted
time: 1483ms
memory: 4008kb
input:
1000 5000 515 362 577 362 6333 740731 965199 187 990 10360 809082 584738 265 667 12394 304855 -840288 528 172 6908 460731 -180949 925 587 16819 397384 -796567 131 783 12526 377282 -6515 875 246 4549 500117 186232 238 759 16131 361172 -555685 564 994 11149 45212 590362 730 810 11212 353913 247112 26 ...
output:
144823713 -248197179239599
result:
ok 2 number(s): "144823713 -248197179239599"
Test #44:
score: 0
Accepted
time: 1541ms
memory: 4060kb
input:
1000 5000 377 971 218 432 6164 14417 625673 53 246 6954 475442 960998 843 791 20186 187234 324378 319 506 6097 20757 -521230 896 808 20639 529583 -10866 521 289 9267 167241 745577 404 722 8010 867178 -226178 832 373 14508 718821 -136773 919 44 7499 750069 -98328 52 189 11899 913637 -587851 470 16 14...
output:
100552728 -269145914555129
result:
ok 2 number(s): "100552728 -269145914555129"
Test #45:
score: 0
Accepted
time: 1447ms
memory: 3964kb
input:
1000 5000 395 496 242 68 44639 849642 634662 322 852 37495 699776 473640 406 404 11526 506183 547552 692 993 30357 899002 -938946 983 274 10503 89183 -724703 766 161 116665 621828 -434027 251 21 21713 56887 -285514 179 136 0 842737 691203 943 307 24361 206123 -402023 895 148 17189 113651 904898 144 ...
output:
74126055 -304903466992658
result:
ok 2 number(s): "74126055 -304903466992658"
Test #46:
score: 0
Accepted
time: 1488ms
memory: 3960kb
input:
1000 5000 879 977 422 3 23737 496496 794736 845 843 8019 611198 56216 549 101 3899 868299 -724064 193 920 24925 909932 -680765 125 311 21367 31620 242826 607 592 8400 132680 458133 232 283 5630 554059 -587186 487 165 31022 595329 841358 367 745 11640 756686 -781994 986 543 13341 31253 334440 332 227...
output:
74199730 -306957895488542
result:
ok 2 number(s): "74199730 -306957895488542"
Test #47:
score: 0
Accepted
time: 887ms
memory: 4036kb
input:
1000 5000 801 651 361 185 5553 862932 752974 680 328 18329 546156 111886 359 241 15577 236613 -863333 409 776 1473 347863 189783 509 174 3949 767905 -888057 60 37 17055 80697 -969959 604 163 14273 803517 -397078 664 572 4284 758103 760919 432 991 15056 360536 992644 83 4 11582 909733 108486 109 922 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #48:
score: 0
Accepted
time: 1445ms
memory: 3940kb
input:
1000 5000 366 572 480 708 14920 366695 968540 712 119 54509 399398 389553 181 572 2843 870921 267895 353 229 8635 393860 -5245 856 511 6125 609060 -256787 611 729 4124 924518 270694 485 184 1541 676296 726111 958 686 6215 938551 914636 596 472 6545 910185 187068 510 153 9478 336865 -862897 626 938 3...
output:
76123109 -303819017690863
result:
ok 2 number(s): "76123109 -303819017690863"
Test #49:
score: 0
Accepted
time: 1610ms
memory: 3940kb
input:
1000 5000 80 300 611 260 21096 497076 42907 495 418 39685 267827 693705 944 122 9442 658753 54999 936 362 13040 108189 869000 511 300 2701 423986 -766165 195 997 12684 108839 374264 81 283 47107 504860 -144173 33 304 99839 868704 -465663 906 147 12865 92924 -784253 440 284 4378 577584 856259 835 713...
output:
80413796 -258653719624958
result:
ok 2 number(s): "80413796 -258653719624958"
Test #50:
score: 0
Accepted
time: 1376ms
memory: 4032kb
input:
1000 5000 491 189 5 571 7775 898777 410199 456 189 18546 399814 -492807 318 118 18018 551961 -572242 296 19 10626 21661 781489 491 322 25681 739193 -352920 619 351 16350 257366 -765023 145 159 10664 113363 -25733 108 728 10957 970706 893617 94 866 34544 591659 252634 977 152 23327 783294 -680794 807...
output:
76300839 -295224850280014
result:
ok 2 number(s): "76300839 -295224850280014"
Test #51:
score: 0
Accepted
time: 1395ms
memory: 4028kb
input:
1000 5000 624 211 677 963 8381 683092 495356 203 404 4075 177895 341880 289 656 28350 872936 -868758 838 728 2957 413978 -199379 288 926 16783 379769 -411974 957 712 11395 224204 537658 436 211 85368 649190 134245 186 797 8029 742355 -577541 354 277 6819 22296 -373919 833 451 18936 137827 282544 246...
output:
317994083 -116441746476196
result:
ok 2 number(s): "317994083 -116441746476196"
Test #52:
score: 0
Accepted
time: 1436ms
memory: 3940kb
input:
1000 5000 900 967 242 967 17078 513941 582905 895 278 13118 370483 871998 636 282 2871 92430 875551 364 882 7048 253843 -15333 81 129 24863 367479 -414480 952 35 57437 427346 426196 900 768 13153 226737 570567 840 967 20460 26394 -335929 900 718 8481 577594 669288 917 417 24358 267262 569835 197 644...
output:
341738518 -79763660364456
result:
ok 2 number(s): "341738518 -79763660364456"
Test #53:
score: 0
Accepted
time: 1466ms
memory: 3964kb
input:
1000 5000 15 153 217 482 14799 868861 199814 718 74 6279 565002 218354 852 179 12994 418209 -797309 863 153 9860 969548 -265651 236 981 5067 278742 874027 566 348 0 858227 -55352 728 537 30793 270111 728984 448 252 19803 288897 -913514 220 74 1849 82181 528776 809 786 11646 390174 -476272 561 591 85...
output:
322000936 -136244459593170
result:
ok 2 number(s): "322000936 -136244459593170"
Test #54:
score: 0
Accepted
time: 1226ms
memory: 4032kb
input:
1000 5000 376 700 272 111 3473 649716 374234 579 74 4351 484039 -695712 38 108 18880 900175 904069 64 280 13591 874364 877132 749 700 2621 853505 754126 100 700 5913 897769 -766687 878 700 7702 223746 -494795 854 700 7902 152561 912948 377 887 41035 294218 -137141 376 487 4344 761067 -797453 711 45 ...
output:
401097621 -95489447383864
result:
ok 2 number(s): "401097621 -95489447383864"
Test #55:
score: 0
Accepted
time: 1212ms
memory: 4028kb
input:
1000 5000 331 384 837 384 9217 851000 660225 326 606 44166 606427 528527 663 384 7771 112057 492577 981 870 4246 336180 -239733 679 26 2193 974910 -515992 572 384 20024 291812 -879414 803 174 4942 737073 -652149 692 631 818 886838 774780 300 218 29851 778316 67581 331 697 4923 698601 -661928 653 563...
output:
400326981 -88424295809831
result:
ok 2 number(s): "400326981 -88424295809831"
Test #56:
score: 0
Accepted
time: 1273ms
memory: 3968kb
input:
1000 5000 446 569 669 209 17884 899363 -785074 182 288 2862 635694 -80875 299 508 28337 924297 643185 168 950 2389 365517 -364776 737 569 3486 869075 404647 217 52 5267 176272 78074 93 870 43906 464626 211361 446 310 8208 484302 -941722 446 28 4979 800714 -14708 446 873 7451 372003 216509 37 875 173...
output:
401478586 -98602206576104
result:
ok 2 number(s): "401478586 -98602206576104"