QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#68844 | #5244. Drzewa rozpinające [A] | Qingyu | 9 | 1301ms | 102008kb | C++23 | 7.4kb | 2022-12-21 11:22:25 | 2022-12-21 11:22:26 |
Judging History
answer
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define st first
#define nd second
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vll = vector<ll>;
#ifdef LOCAL
mt19937 rng(69);
#else
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
const int mod = 1000 * 1000 * 1000 + 7;
const int kMaxVal = 5010;
uniform_int_distribution uniform_mod_p(1, mod - 1);
// Berlekamp-Massey z biblioteczki UW
namespace Massey {
void add_self(int & a, int b) { a += b; if(a >= mod) a -= mod; }
void sub_self(int & a, int b) { a -= b; if(a < 0) a += mod; }
int mul(int a, int b) { return (ll) a * b % mod; }
int my_pow(int a, int b) {
int r = 1;
while(b) {
if(b % 2) r = mul(r, a);
a = mul(a, a);
b /= 2;
}
return r;
}
int my_inv(int a) { return my_pow(a, mod - 2); }
struct Massey {
vector<int> start, coef; // 3 optional lines
vector<vector<int>> powers;
int memo_inv;
bool ok;
// Start here and write the next ~25 lines until "STOP"
int L; // L == coef.size() <= start.size()
Massey(vector<int> in) : ok{true} { // O(N^2)
L = 0;
const int N = in.size();
vector<int> C{1}, B{1};
for(int n = 0; n < N; ++n) {
assert(0 <= in[n] && in[n] < mod); // invalid input
B.insert(B.begin(), 0);
int d = 0;
for(int i = 0; i <= L; ++i)
add_self(d, mul(C[i], in[n-i]));
if(d == 0) continue;
vector<int> T = C;
C.resize(max(B.size(), C.size()));
for(int i = 0; i < (int) B.size(); ++i)
sub_self(C[i], mul(d, B[i]));
if(2 * L <= n) {
L = n + 1 - L;
B = T;
d = my_inv(d);
for(int & x : B) x = mul(x, d);
}
}
//~ cerr << "L = " << L << "\n";
if (2 * L > N - 2) {
ok = false;
}
// === STOP ===
for(int i = 1; i < (int) C.size(); ++i)
coef.push_back((mod - C[i]) % mod);
assert((int) coef.size() == L);
for(int i = 0; i < L; ++i)
start.push_back(in[i]);
while(!coef.empty() && !coef.back()) { coef.pop_back(); --L; }
if(!coef.empty()) memo_inv = my_inv(coef.back());
powers.push_back(coef);
}
};
} /* namespace Massey */
inline void add_mod(int &a, int b) {
a += b;
if (a >= mod) { a -= mod; }
}
inline void sub_mod(int &a, int b) {
a -= b;
if (a < 0) { a += mod; }
}
inline int mul_mod(int a, int b) {
return (int)((ll)a * b % mod);
}
inline int pow_mod(int a, int n) {
int r = 1;
while (n) {
if (n & 1) { r = mul_mod(r, a); }
n >>= 1;
a = mul_mod(a, a);
}
return r;
}
inline int inv_mod(int a) {
return pow_mod(a, mod - 2);
}
inline int div_mod(int a, int b) {
return mul_mod(a, inv_mod(b));
}
int input_n;
int mat_n;
vi elems;
int phi[kMaxVal];
int gcds[kMaxVal][kMaxVal];
vi input_row_sums;
template <typename T>
std::vector<T> BasicSieve(T max_range) {
std::vector<T> min_prime(max_range + 1);
std::iota(min_prime.begin(), min_prime.end(), 0);
for (T p = 2; p * p <= max_range; ++p) {
if (min_prime[p] != p) { continue; }
for (T i = p * p; i <= max_range; i += p) {
if (min_prime[i] == i) {
min_prime[i] = p;
}
}
}
return min_prime;
}
void Preproc() {
auto sieve = BasicSieve(kMaxVal);
for (int value = 1; value < kMaxVal; ++value) {
int x = value, y = value;
while (y > 1) {
const int p = sieve[y];
x = (x / p) * (p - 1);
while (y % p == 0) { y /= p; }
}
phi[value] = x;
}
for (int i = 0; i < kMaxVal; ++i) {
gcds[0][i] = gcds[i][0] = i;
}
for (int i = 1; i < kMaxVal; ++i) {
for (int j = 1; j < kMaxVal; ++j) {
if (i >= j) {
gcds[i][j] = gcds[i - j][i];
} else {
gcds[i][j] = gcds[i][j - i];
}
}
}
}
ll x_vec_helper[kMaxVal];
ll y_vec_helper[kMaxVal];
void MultiplyVecByLaplacian(vi &in_vec) {
memset(x_vec_helper, 0, sizeof(x_vec_helper));
memset(y_vec_helper, 0, sizeof(y_vec_helper));
for (int i = 0; i < SZ(in_vec); ++i) {
x_vec_helper[elems[i]] += in_vec[i];
x_vec_helper[elems[i]] %= mod;
}
for (int d = 1; d < kMaxVal; ++d) {
ll val = 0;
for (int i = d; i < kMaxVal; i += d) {
val += x_vec_helper[i];
}
y_vec_helper[d] = (val * phi[d]) % mod;
}
memset(x_vec_helper, 0, sizeof(x_vec_helper));
for (int d = 1; d < kMaxVal; ++d) {
for (int i = d; i < kMaxVal; i += d) {
x_vec_helper[i] += y_vec_helper[d];
}
}
for (int i = 0; i < SZ(in_vec); ++i) {
ll ans = x_vec_helper[elems[i]];
ans -= (ll)elems[i] * in_vec[i];
ans = -ans;
ans += (ll)in_vec[i] * input_row_sums[i];
ans %= mod;
if (ans < 0) { ans += mod; }
in_vec[i] = ans;
//~ ans[i] = x_vec_helper[elems[i]] % mod;
//~ sub_mod(ans[i], mul_mod(elems[i], in_vec[i]));
//~ if (ans[i]) {
//~ ans[i] = mod - ans[i];
//~ }
//~ add_mod(ans[i], mul_mod(in_vec[i], input_row_sums[i]));
}
//~ return ans;
}
vi GetRandomVector(int len) {
vi ans(len);
for (int i = 0; i < len; ++i) {
ans[i] = uniform_mod_p(rng);
}
return ans;
}
int DotProd(const vi &a, const vi &b) {
int ans = 0;
for (int i = 0; i < SZ(a); ++i) {
add_mod(ans, mul_mod(a[i], b[i]));
}
return ans;
}
int LaplacianDeterminant() {
while (true) {
const vi coef_vec = GetRandomVector(mat_n);
const vi row_scale_vec = GetRandomVector(mat_n);
vi cur_vec = GetRandomVector(mat_n);
const int num_coefs = mat_n * 2 + 10;
vi massey_coefs(num_coefs);
for (int i = 0; i < num_coefs; ++i) {
massey_coefs[i] = DotProd(coef_vec, cur_vec);
MultiplyVecByLaplacian(cur_vec);
for (int j = 0; j < mat_n; ++j) {
cur_vec[j] = mul_mod(cur_vec[j], row_scale_vec[j]);
}
}
Massey::Massey massey(massey_coefs);
if (!massey.ok) { continue; }
debug() << imie(massey.start) << imie(massey.coef);
if (SZ(massey.coef) < mat_n) { continue; }
int det = massey.coef.back();
for (int elem : row_scale_vec) {
det = div_mod(det, elem);
}
if (mat_n % 2 == 0) {
det = (mod - det) % mod;
}
return det;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(11);
cerr << fixed << setprecision(6);
Preproc();
cin >> input_n;
elems.resize(input_n);
for (int &x : elems) { cin >> x; }
if (input_n == 1) {
cout << "1\n";
return 0;
}
mat_n = input_n - 1;
input_row_sums.resize(input_n);
for (int i = 0; i < input_n; ++i) {
for (int j = 0; j < input_n; ++j) {
if (i != j) {
input_row_sums[i] += gcds[elems[i]][elems[j]]; //gcd(elems[i], elems[j]);
}
}
}
cout << LaplacianDeterminant() << "\n";
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 52ms
memory: 101616kb
input:
1 3
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 53ms
memory: 101612kb
input:
2 4 2
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 52ms
memory: 101688kb
input:
3 2 7 5
output:
3
result:
ok single line: '3'
Test #4:
score: 0
Accepted
time: 54ms
memory: 101624kb
input:
4 2 5 5 2
output:
72
result:
ok single line: '72'
Test #5:
score: 0
Accepted
time: 50ms
memory: 101684kb
input:
5 1 8 4 8 4
output:
7225
result:
ok single line: '7225'
Test #6:
score: 0
Accepted
time: 52ms
memory: 101592kb
input:
6 1 6 1 3 4 5
output:
2808
result:
ok single line: '2808'
Test #7:
score: 0
Accepted
time: 55ms
memory: 101528kb
input:
7 2 7 7 1 5 1 8
output:
58653
result:
ok single line: '58653'
Test #8:
score: 0
Accepted
time: 65ms
memory: 101628kb
input:
8 3 8 7 8 6 6 1 7
output:
13854720
result:
ok single line: '13854720'
Test #9:
score: 0
Accepted
time: 51ms
memory: 101652kb
input:
8 1 2 4 8 3 6 7 5
output:
1695744
result:
ok single line: '1695744'
Subtask #2:
score: 1
Accepted
Test #10:
score: 1
Accepted
time: 122ms
memory: 101740kb
input:
500 388 351 42 430 179 19 288 101 447 415 133 236 109 312 15 333 348 119 81 264 67 262 426 279 145 397 210 300 212 40 164 24 373 63 301 482 115 344 60 230 295 456 51 363 224 327 338 110 97 458 274 96 46 135 50 411 499 59 352 191 372 211 91 483 357 15 348 284 94 96 367 281 100 403 212 350 8 111 32 33...
output:
769339415
result:
ok single line: '769339415'
Test #11:
score: 0
Accepted
time: 123ms
memory: 101636kb
input:
496 417 307 448 207 103 190 113 476 114 358 21 423 64 422 363 19 171 246 337 492 18 474 471 267 286 101 126 343 272 179 397 18 318 353 463 403 257 74 355 338 139 309 17 368 330 152 158 281 405 40 323 457 135 157 27 333 71 303 383 122 104 77 436 318 140 268 303 356 85 389 73 330 9 71 214 451 500 375 ...
output:
941145354
result:
ok single line: '941145354'
Test #12:
score: 0
Accepted
time: 124ms
memory: 101644kb
input:
500 302 231 66 338 272 352 89 157 270 23 243 153 177 110 385 127 335 139 394 202 68 138 323 130 461 254 232 178 284 150 148 70 422 288 402 313 327 369 191 404 354 19 425 61 34 259 139 461 71 352 88 137 246 478 163 325 307 367 386 241 201 273 437 361 22 109 363 122 124 490 197 450 472 337 355 142 404...
output:
712927890
result:
ok single line: '712927890'
Test #13:
score: 0
Accepted
time: 123ms
memory: 101740kb
input:
499 63 43 14 76 446 303 375 308 191 481 73 12 340 115 316 341 291 382 448 233 65 229 144 390 333 231 327 410 451 21 221 270 294 372 340 22 490 443 229 351 375 450 445 102 206 417 497 495 181 75 49 416 103 340 393 97 479 61 419 9 412 154 345 228 321 462 261 253 121 268 273 114 369 52 429 80 412 313 1...
output:
57847713
result:
ok single line: '57847713'
Test #14:
score: 0
Accepted
time: 114ms
memory: 101580kb
input:
475 236 288 69 250 254 14 346 224 164 475 257 358 448 399 229 482 239 450 245 222 327 43 102 354 129 324 205 102 428 229 44 468 144 177 224 240 244 188 349 11 196 199 431 449 174 5 161 376 108 473 188 163 269 370 180 367 3 279 7 185 57 413 494 127 132 187 430 77 103 259 433 58 88 219 415 36 141 146 ...
output:
321775138
result:
ok single line: '321775138'
Test #15:
score: 0
Accepted
time: 118ms
memory: 101684kb
input:
486 443 323 386 16 360 296 7 372 431 189 166 84 260 159 146 369 182 108 201 338 129 70 296 132 90 189 102 490 399 234 266 423 404 161 463 269 307 182 11 298 319 497 320 483 18 410 61 288 454 71 101 390 139 21 292 317 199 56 95 408 399 499 31 200 55 40 342 326 425 430 368 478 385 418 400 279 382 193 ...
output:
851424932
result:
ok single line: '851424932'
Test #16:
score: 0
Accepted
time: 123ms
memory: 101744kb
input:
496 295 28 80 174 254 114 137 123 410 179 214 347 458 294 372 423 367 378 337 233 217 50 101 46 105 102 429 271 221 135 175 339 130 101 280 221 212 435 488 193 335 139 173 24 106 294 35 312 191 286 227 426 500 184 275 265 221 176 108 370 307 312 100 498 176 7 15 322 113 454 317 443 217 158 209 97 31...
output:
374621317
result:
ok single line: '374621317'
Test #17:
score: 0
Accepted
time: 116ms
memory: 101584kb
input:
400 218 474 474 483 91 130 68 495 364 450 150 126 464 209 12 442 40 52 116 325 340 64 232 264 171 161 351 62 201 289 450 387 382 270 194 353 55 238 413 22 317 399 489 298 196 478 49 444 156 307 431 321 37 297 342 161 55 375 419 244 139 433 274 407 231 297 165 418 209 474 233 42 154 414 349 329 470 1...
output:
88835088
result:
ok single line: '88835088'
Test #18:
score: 0
Accepted
time: 113ms
memory: 101568kb
input:
500 323 276 88 45 387 142 224 7 237 484 226 485 206 464 295 149 393 22 158 448 418 162 421 64 339 5 391 230 260 278 8 179 337 138 170 104 400 266 95 223 25 328 406 107 37 496 315 190 26 208 426 47 333 353 290 369 291 352 211 444 66 351 219 15 381 150 115 257 146 389 42 461 136 431 459 102 222 441 34...
output:
221110509
result:
ok single line: '221110509'
Subtask #3:
score: 1
Accepted
Test #19:
score: 1
Accepted
time: 198ms
memory: 101712kb
input:
1000 610 997 196 509 978 104 682 466 660 969 406 839 987 15 916 440 364 420 29 997 685 944 943 75 64 51 838 481 779 833 269 678 447 948 626 293 220 961 529 868 337 492 13 953 207 949 845 537 910 694 212 425 14 682 203 351 99 970 567 530 785 779 331 312 494 961 66 60 912 881 409 291 652 740 757 936 8...
output:
871865263
result:
ok single line: '871865263'
Test #20:
score: 0
Accepted
time: 199ms
memory: 101596kb
input:
994 934 177 454 636 741 823 994 374 578 921 683 587 128 416 52 397 598 108 384 415 446 865 963 305 309 514 736 270 95 973 729 372 168 361 453 586 410 748 46 279 646 92 96 698 624 24 938 278 298 338 595 356 811 526 852 42 907 628 339 315 637 376 907 915 976 841 115 217 239 344 790 167 823 528 326 786...
output:
58615766
result:
ok single line: '58615766'
Test #21:
score: 0
Accepted
time: 196ms
memory: 101688kb
input:
999 368 805 987 787 441 573 926 78 758 275 270 796 204 731 614 620 462 82 45 231 345 131 500 868 468 851 71 224 33 149 849 261 638 871 270 922 471 546 443 93 336 988 846 518 766 275 207 280 500 752 447 488 185 765 495 141 784 30 520 638 944 957 600 476 451 174 33 448 723 136 42 101 91 364 552 849 61...
output:
312396414
result:
ok single line: '312396414'
Test #22:
score: 0
Accepted
time: 192ms
memory: 101592kb
input:
980 842 980 762 39 36 319 836 604 921 145 372 645 620 58 867 63 933 412 689 590 27 688 358 824 467 279 997 820 60 191 943 115 394 14 28 759 869 392 809 487 507 837 124 685 935 238 954 308 280 758 189 673 662 605 155 868 627 137 982 815 414 943 287 911 498 721 22 651 826 448 795 958 251 369 989 285 2...
output:
292829341
result:
ok single line: '292829341'
Test #23:
score: 0
Accepted
time: 188ms
memory: 101620kb
input:
996 265 357 782 637 666 532 692 208 621 586 830 189 561 441 234 230 854 461 886 85 715 494 584 161 755 156 546 731 134 14 284 407 965 724 449 970 464 227 282 451 453 442 829 958 864 349 163 777 460 820 524 281 999 706 903 360 3 277 937 72 986 975 598 293 113 116 213 746 756 921 769 816 696 114 388 9...
output:
331950801
result:
ok single line: '331950801'
Test #24:
score: 0
Accepted
time: 203ms
memory: 101656kb
input:
998 276 47 157 205 422 211 525 204 177 699 5 593 998 886 8 578 851 625 15 944 189 323 592 160 151 337 308 171 632 335 630 295 833 945 548 627 208 730 173 661 463 677 714 782 115 472 403 605 210 956 397 528 22 379 121 107 470 99 724 865 733 25 228 281 783 296 58 300 525 444 627 56 57 698 122 374 319 ...
output:
505709469
result:
ok single line: '505709469'
Test #25:
score: 0
Accepted
time: 207ms
memory: 101700kb
input:
920 29 607 334 904 116 266 702 400 861 380 136 952 874 250 224 589 402 806 698 243 605 900 84 309 814 632 667 232 808 185 886 570 321 452 660 69 17 41 280 37 41 296 476 612 718 854 651 273 420 919 661 496 407 144 757 813 475 317 723 473 753 160 531 146 146 504 882 300 514 204 182 757 504 480 681 307...
output:
604762033
result:
ok single line: '604762033'
Test #26:
score: 0
Accepted
time: 185ms
memory: 101636kb
input:
895 636 22 127 748 28 143 578 259 356 505 704 406 226 101 402 17 485 656 133 144 631 488 420 743 23 152 1 10 409 187 877 802 164 371 687 4 494 473 356 16 468 94 141 916 999 582 828 502 482 165 393 37 738 310 725 682 256 600 288 425 833 191 442 706 569 145 251 920 990 856 541 750 906 855 50 760 516 5...
output:
339450845
result:
ok single line: '339450845'
Test #27:
score: 0
Accepted
time: 201ms
memory: 101776kb
input:
1000 689 927 391 418 53 701 625 340 874 107 324 901 31 151 943 581 994 174 351 311 259 816 872 122 711 906 881 384 759 647 330 388 376 190 998 932 268 59 629 152 907 815 964 119 889 567 509 132 91 842 832 323 357 710 39 671 560 780 926 638 443 684 518 430 546 199 487 772 786 247 58 328 155 840 447 1...
output:
194280610
result:
ok single line: '194280610'
Subtask #4:
score: 1
Accepted
Test #28:
score: 1
Accepted
time: 658ms
memory: 101884kb
input:
3200 1539 1480 1859 627 831 1495 1865 2906 1303 1232 1167 206 489 1045 2498 693 2846 2137 3184 1200 1396 1065 1418 2769 2659 1054 600 2248 559 2974 2691 241 2693 819 970 493 1360 1579 2599 2158 326 869 1370 356 415 885 899 2826 1235 2958 555 1150 2190 1952 502 1390 701 1141 2678 2669 769 2917 2439 4...
output:
577129468
result:
ok single line: '577129468'
Test #29:
score: 0
Accepted
time: 553ms
memory: 101776kb
input:
2763 725 1548 1680 1786 1395 587 3122 1105 2089 2843 819 363 1686 1952 1748 739 2343 2783 1200 3016 2428 1833 2044 2944 1320 3193 2335 3106 560 966 2264 1854 730 2228 2119 1644 3167 812 2824 127 2618 317 2674 1063 261 928 2950 1705 212 1914 1081 1012 1601 102 3031 2343 2287 1796 2300 1313 3091 2202 ...
output:
273161825
result:
ok single line: '273161825'
Test #30:
score: 0
Accepted
time: 641ms
memory: 101804kb
input:
3200 2798 3025 1999 345 2265 811 1257 1721 2491 990 3061 2064 979 59 1985 2863 1109 179 2645 2003 358 226 2930 1844 2260 1858 1490 2890 2522 2525 2621 2071 1358 623 2860 2057 2114 2030 1111 283 71 1259 2249 737 555 2721 35 2122 1660 638 1000 3137 50 540 2065 1074 1189 2370 853 1892 1358 3034 2246 19...
output:
125930119
result:
ok single line: '125930119'
Test #31:
score: 0
Accepted
time: 633ms
memory: 101928kb
input:
3198 880 73 483 2149 669 2554 470 3010 1800 962 2262 1316 3138 221 3079 902 3101 1060 1909 1277 55 735 993 2754 1448 1639 600 1747 3183 2869 1535 182 344 574 1191 2580 1198 94 2132 2762 1684 1620 309 2364 1174 545 2747 3064 2289 1929 2384 2702 1051 1755 1993 2341 2735 1861 785 3192 3048 57 2565 984 ...
output:
443501882
result:
ok single line: '443501882'
Test #32:
score: 0
Accepted
time: 627ms
memory: 101916kb
input:
3200 2552 1803 2077 2728 41 2620 650 276 2085 1975 2857 1591 755 2859 54 2524 1417 393 3052 3032 716 2294 331 1240 2895 1179 38 3140 1712 1514 1328 1672 335 1969 2478 2238 2353 19 1455 790 1832 433 1435 2676 2752 2921 1139 1919 341 2698 724 258 1178 1279 3153 357 2464 3001 1266 500 581 1960 205 2149...
output:
188519840
result:
ok single line: '188519840'
Test #33:
score: 0
Accepted
time: 638ms
memory: 101788kb
input:
3200 377 1034 499 1549 2833 1249 1068 3107 773 2771 2438 1674 3121 2062 836 18 1110 2233 704 2684 2692 2734 1354 2779 1233 1931 2990 2617 503 1758 3116 736 2944 2551 2619 454 2067 2218 1546 532 2985 2518 2430 1430 2396 1894 1065 1001 1676 1077 1644 2074 1298 2561 254 2695 957 1521 2940 1013 875 1460...
output:
761031949
result:
ok single line: '761031949'
Test #34:
score: 0
Accepted
time: 646ms
memory: 101788kb
input:
3199 53 2445 338 2790 251 2583 1375 304 2908 1278 2916 143 1612 1591 1879 2229 848 1977 2077 2642 109 2743 1531 1371 1745 582 1857 650 12 939 2321 2579 3126 179 1200 2034 1177 2981 825 222 281 612 3089 779 756 1213 2979 234 1749 761 1340 1216 231 1185 1962 1154 2701 2919 2801 1544 1221 3190 4 1003 8...
output:
15706462
result:
ok single line: '15706462'
Test #35:
score: 0
Accepted
time: 615ms
memory: 101764kb
input:
3109 2861 68 709 3005 991 1536 606 2149 480 1017 503 494 1402 2744 1656 810 2517 373 490 2595 2520 2569 503 268 2390 2543 478 214 3122 123 1433 529 686 2529 1105 3141 2433 939 1705 182 1021 1399 503 2734 2894 2554 3165 21 3176 731 1734 2687 813 55 1660 2728 2449 2686 2650 1746 1933 2210 223 2821 169...
output:
1779025
result:
ok single line: '1779025'
Test #36:
score: 0
Accepted
time: 641ms
memory: 101744kb
input:
3200 1941 2491 2055 504 2728 928 2517 1572 151 810 2225 545 1270 728 672 2050 1390 2381 2471 802 812 2014 1693 746 1179 3013 2310 208 2775 1664 1522 594 1250 2291 2364 7 2131 2202 1643 1141 1243 3176 522 346 1955 2032 69 2842 1760 1884 1582 2611 14 259 2665 1790 426 2244 2458 143 1775 1772 1121 140 ...
output:
440419712
result:
ok single line: '440419712'
Subtask #5:
score: 1
Accepted
Test #37:
score: 1
Accepted
time: 710ms
memory: 101864kb
input:
3500 874 1486 3240 2876 2120 552 2467 665 880 365 1254 2025 1339 197 688 3131 3384 3317 2145 1045 2117 2529 2428 2795 3078 2577 1872 2668 502 975 544 390 1499 2288 1721 1930 19 2098 3242 1350 182 2448 679 2359 944 1016 979 3059 2288 1169 179 166 144 1577 2956 270 2157 2698 2438 650 3274 1057 2515 21...
output:
662636110
result:
ok single line: '662636110'
Test #38:
score: 0
Accepted
time: 709ms
memory: 101936kb
input:
3485 209 1328 2970 1314 810 119 61 2760 1032 2328 1294 1993 1106 1708 1160 2492 1817 2677 1517 1719 2453 2347 2643 2804 3216 3288 2206 3098 2011 3327 711 2878 3284 2230 1175 1002 1152 1119 3454 1226 3015 774 763 604 2334 1126 220 2705 2922 779 726 1983 1396 3097 833 3455 2444 2148 2156 130 845 206 2...
output:
230966022
result:
ok single line: '230966022'
Test #39:
score: 0
Accepted
time: 706ms
memory: 101800kb
input:
3500 130 620 2281 2764 703 1942 1760 2615 411 782 1612 1118 1405 3002 1246 1256 3044 2228 648 1499 252 2660 1062 179 1856 2614 3431 1867 2536 1908 1412 217 2877 1256 718 699 642 1948 2562 2624 1301 260 1548 2586 2548 1470 1075 276 78 3179 2200 2598 2586 61 1646 1382 957 3161 3174 2244 1819 1934 373 ...
output:
995000768
result:
ok single line: '995000768'
Test #40:
score: 0
Accepted
time: 696ms
memory: 101832kb
input:
3441 3057 2394 2308 3129 1888 486 498 48 2805 193 3046 797 2411 3000 524 931 2645 105 772 858 1676 2166 3403 1000 2249 1141 1631 736 3320 506 2107 3333 1847 2569 1070 1710 2295 114 2865 211 1201 1723 2544 1481 1758 2642 390 1050 2896 2984 2930 2582 1868 115 339 2850 3025 3221 2984 411 35 1250 628 13...
output:
487286339
result:
ok single line: '487286339'
Test #41:
score: 0
Accepted
time: 703ms
memory: 101872kb
input:
3471 3469 2517 3402 2885 219 1888 2520 2108 1144 6 1415 1216 1208 3383 2317 1901 2250 2909 3139 922 2674 747 2584 1025 1812 2553 2648 2677 1477 3335 938 2676 2261 2113 3099 561 1351 1980 781 379 2369 32 1207 2553 2854 1950 2074 3425 1061 1499 1087 1933 1710 1467 1225 2926 3133 2829 455 2381 119 2861...
output:
202530793
result:
ok single line: '202530793'
Test #42:
score: 0
Accepted
time: 718ms
memory: 101884kb
input:
3337 1450 1802 122 2794 2025 2155 2642 592 1287 2501 3170 584 2210 714 1700 1192 301 2118 1595 3345 886 1372 642 371 2848 3227 1294 2601 2799 2629 2793 1269 1045 2062 2863 375 2846 172 608 3360 2891 56 1015 3265 1402 307 1443 2065 1719 764 3360 3086 2474 870 2548 964 627 1084 60 3195 1583 2832 3030 ...
output:
311057806
result:
ok single line: '311057806'
Test #43:
score: 0
Accepted
time: 677ms
memory: 101856kb
input:
3288 666 1575 3044 1008 2797 1578 885 2115 3249 2815 2198 517 800 2752 520 2395 695 2981 3157 781 958 3445 1890 568 1893 977 3198 2651 2985 3322 1737 1204 3187 2414 2883 1657 2271 734 3443 2342 119 3401 2431 2398 368 436 1210 2066 2057 953 3003 2607 2317 2760 2126 946 554 1559 2949 598 827 1449 812 ...
output:
821958151
result:
ok single line: '821958151'
Test #44:
score: 0
Accepted
time: 726ms
memory: 101788kb
input:
3497 381 1280 3026 2170 1750 1417 2028 1366 2486 778 1494 3195 709 2638 3004 2217 2070 1590 1840 2356 165 2277 2975 1219 1000 3080 3273 458 54 1375 1654 2563 180 2099 1055 2871 73 2038 2812 2494 3264 2520 2473 621 777 2982 2043 2441 1309 1103 610 2742 1118 2503 1238 2175 2308 361 1026 3375 2334 2117...
output:
212084753
result:
ok single line: '212084753'
Test #45:
score: 0
Accepted
time: 731ms
memory: 101804kb
input:
3500 2616 951 2749 308 1968 3047 2401 1298 558 98 2980 3451 2212 3110 374 3024 40 1239 2213 3145 849 3113 2442 2062 1633 2722 1534 1992 3252 26 2258 1472 453 1175 3128 1096 3133 2645 2160 329 3315 2302 674 1145 3149 3336 339 2400 3245 2828 2831 2657 2561 88 3043 1680 1437 3435 1289 1646 1164 2620 33...
output:
113224628
result:
ok single line: '113224628'
Subtask #6:
score: 1
Accepted
Test #46:
score: 1
Accepted
time: 818ms
memory: 101944kb
input:
3800 2315 2518 662 2648 1371 1971 2374 499 294 2460 1071 230 503 206 140 766 3094 3071 3370 1300 3118 1209 3666 972 2220 1827 440 45 674 865 1929 1207 2824 1213 350 1786 2647 702 3616 788 1616 3463 2524 794 786 234 774 319 1810 2563 3469 1134 3665 1316 684 3587 3604 1256 1060 3119 1290 3200 1330 128...
output:
167155508
result:
ok single line: '167155508'
Test #47:
score: 0
Accepted
time: 830ms
memory: 101904kb
input:
3797 2370 3057 2025 2932 892 2591 2826 2633 2705 745 1952 288 1058 2908 1953 1389 502 482 1099 3675 205 25 3519 119 2432 138 2164 2262 2281 1022 170 2091 3453 1072 2733 791 807 2108 2044 1838 2033 2833 1454 649 1092 71 718 448 887 2162 2521 3651 3416 1887 228 3280 2839 1251 2730 1484 2641 2880 1536 ...
output:
31533947
result:
ok single line: '31533947'
Test #48:
score: 0
Accepted
time: 803ms
memory: 101884kb
input:
3786 622 3195 578 1149 2882 952 1819 1630 775 238 2219 3381 813 1480 3275 1081 1331 961 2497 412 2866 1359 3507 1415 1725 2770 227 1837 495 2993 592 1211 1301 1357 1731 739 1165 1137 2877 1851 2323 2612 748 2322 2160 1985 3073 1735 1515 3328 2881 2671 3621 117 1085 677 883 1215 2561 3702 1807 2412 6...
output:
873352859
result:
ok single line: '873352859'
Test #49:
score: 0
Accepted
time: 796ms
memory: 101936kb
input:
3800 252 3054 577 2889 728 2981 1680 1678 993 728 934 357 3436 3634 3355 819 1913 829 2011 3123 3005 1704 3051 367 806 2381 1431 372 2517 2518 84 2174 411 2265 1012 3690 1148 3760 1609 3599 3755 1468 1469 641 879 2255 2358 2717 2466 1033 1941 127 2343 2765 3054 1154 1861 3064 1426 581 143 44 2984 58...
output:
453629067
result:
ok single line: '453629067'
Test #50:
score: 0
Accepted
time: 806ms
memory: 101820kb
input:
3797 3591 3034 1652 744 233 1914 1788 806 3140 1281 2170 340 1253 1525 2464 1725 3736 2372 737 2487 979 3520 2656 1276 1755 1440 304 3548 3214 1715 3252 1292 329 2460 1800 165 2251 3404 310 1876 898 811 1969 3418 3769 2844 2671 2492 2848 2475 473 1505 182 1054 3368 1346 69 300 3078 970 788 3106 849 ...
output:
742795604
result:
ok single line: '742795604'
Test #51:
score: 0
Accepted
time: 469ms
memory: 101872kb
input:
2355 3364 1960 3113 17 2251 1120 1826 1892 252 2387 2578 538 1348 2293 2688 979 513 1464 3097 2246 3347 3305 1040 2497 3626 3648 43 3265 3061 3440 304 2598 2255 3212 2700 2178 1803 3034 2480 896 769 1580 1059 1676 2079 3196 2138 529 1899 1804 1878 1159 3609 2654 2688 437 483 798 1376 1829 3712 1195 ...
output:
40083733
result:
ok single line: '40083733'
Test #52:
score: 0
Accepted
time: 807ms
memory: 101936kb
input:
3795 2726 1129 1935 3349 444 1621 1156 3238 3532 251 1727 3596 2759 1981 967 581 2760 3443 219 3213 751 1334 1732 1900 2859 2609 3501 405 785 383 3707 2747 2766 1441 669 529 2168 1863 923 3547 798 74 900 2189 21 2252 329 1923 454 1366 1912 1962 3756 3044 1892 3570 2229 1922 46 3487 2994 1207 316 804...
output:
734144360
result:
ok single line: '734144360'
Test #53:
score: 0
Accepted
time: 373ms
memory: 101828kb
input:
1911 3601 3090 633 220 508 2623 3552 1620 874 3729 3311 2120 3590 751 2816 2475 2220 1613 2788 3483 2309 3143 729 856 91 647 2416 1779 1276 2366 144 2229 2327 3262 2228 1321 3405 465 1738 3444 209 1821 1133 2117 2342 518 2462 640 756 1838 214 169 1862 3035 2302 699 3383 3199 431 2234 1283 3601 1169 ...
output:
677562373
result:
ok single line: '677562373'
Test #54:
score: 0
Accepted
time: 816ms
memory: 101848kb
input:
3800 3143 2270 2817 125 3646 2645 1117 1968 401 709 2649 1676 3212 1679 1964 278 2146 2227 572 2090 1579 2872 1048 690 1633 231 1016 2016 2692 2267 908 3722 3253 374 150 3336 1474 556 1532 3399 1278 1246 3528 578 2998 2304 109 1073 101 145 769 3370 3547 175 2178 2604 1379 647 657 3539 3247 550 694 2...
output:
30270699
result:
ok single line: '30270699'
Subtask #7:
score: 1
Accepted
Test #55:
score: 1
Accepted
time: 887ms
memory: 101832kb
input:
4100 686 3769 3413 2407 3553 855 3799 2773 3379 1826 3852 1087 1268 247 3521 3935 463 219 1771 2172 1210 2889 2074 867 3403 3107 2392 1502 1346 911 612 1643 1552 2626 885 2903 3218 4055 1013 1641 2892 2100 291 2173 1634 992 1187 3539 2193 1168 3716 1310 1698 3830 1958 2061 2995 909 2913 1805 810 912...
output:
757097793
result:
ok single line: '757097793'
Test #56:
score: 0
Accepted
time: 855ms
memory: 101812kb
input:
3994 1076 3896 3574 3644 3866 1554 491 2424 3297 2077 3240 952 1650 1929 252 2543 3715 3659 1615 2403 86 3912 3806 1986 2556 1083 622 502 2240 1817 3024 2462 2346 4053 564 933 4061 3539 4012 1891 3628 2236 3474 2709 2953 2801 2263 3967 1603 3662 2041 498 3119 1255 791 3263 3932 371 72 1255 1859 1341...
output:
241505224
result:
ok single line: '241505224'
Test #57:
score: 0
Accepted
time: 859ms
memory: 101852kb
input:
4023 2744 2911 3416 521 1958 122 2558 2409 1808 3915 2217 1569 2692 2787 4007 1725 1103 1967 3437 2891 2904 3472 3256 3724 3447 3784 2931 127 1149 4098 3319 2658 123 1975 3850 3207 206 331 251 3742 3848 1655 2868 2634 1953 1240 65 2576 1096 3577 277 3270 2022 260 3088 3731 2571 3924 2030 3535 3417 1...
output:
637570874
result:
ok single line: '637570874'
Test #58:
score: 0
Accepted
time: 897ms
memory: 101840kb
input:
4097 1530 142 1889 2770 417 333 3462 2622 1839 3357 3422 4075 3983 593 913 1009 3715 384 1433 2802 3169 2941 1395 231 30 1118 3180 3403 2212 473 783 819 2338 123 850 2629 724 3687 2598 1543 4089 4013 579 107 3374 1062 1023 179 2771 273 3737 3586 2444 959 2074 1103 1700 1956 2045 2104 543 990 3194 18...
output:
96711327
result:
ok single line: '96711327'
Test #59:
score: 0
Accepted
time: 928ms
memory: 101836kb
input:
4098 2336 459 2702 21 2593 286 427 2509 1537 2637 786 3552 3805 2629 3418 1470 3075 3474 1097 1666 2844 1966 9 2200 985 906 2524 307 3242 2222 2167 2078 3071 3978 1465 1792 1734 2189 3499 3188 2275 4085 1016 2961 775 2679 1879 968 3717 4077 3217 872 808 3764 1497 390 1586 1648 3414 1247 1796 6 2030 ...
output:
184295244
result:
ok single line: '184295244'
Test #60:
score: 0
Accepted
time: 623ms
memory: 101808kb
input:
3108 1631 2434 2094 2755 3953 260 2495 2343 2706 2994 3658 141 2602 1205 1058 639 1949 3810 2913 648 422 2564 811 1312 45 1530 3321 2933 1980 2125 1113 2038 1550 3876 76 2953 1830 1923 1582 2356 1175 4036 3068 320 1803 3917 2418 1095 4031 2235 2146 3050 812 3874 437 263 341 2550 1259 309 4061 1521 2...
output:
76749403
result:
ok single line: '76749403'
Test #61:
score: 0
Accepted
time: 826ms
memory: 101728kb
input:
3837 2844 3035 2511 226 2670 2910 1547 1872 3153 2351 1352 3418 319 2558 1820 992 355 1567 1382 984 1744 11 3980 720 168 3679 2780 196 2632 3689 4047 3055 570 2211 817 78 2243 537 632 2137 2827 187 2791 371 3803 1754 169 3319 1346 1573 3375 728 776 2786 914 2742 1676 2971 3991 3311 2579 3297 1222 22...
output:
941515195
result:
ok single line: '941515195'
Test #62:
score: 0
Accepted
time: 917ms
memory: 101924kb
input:
4098 2051 2111 456 3955 4093 2161 3770 3361 3463 528 89 2478 2012 1035 41 3592 3799 1087 2111 3633 579 1980 1601 2893 456 3821 2562 2651 350 65 2304 3397 51 986 159 1349 3303 718 3595 39 3018 2159 3799 2070 2396 2036 2092 583 1575 2856 454 1726 1301 3593 2238 4060 3983 2573 1556 228 716 1010 3057 22...
output:
941084789
result:
ok single line: '941084789'
Test #63:
score: 0
Accepted
time: 883ms
memory: 101964kb
input:
4100 1086 328 2338 2629 239 3279 975 2936 217 2776 1269 408 1164 3603 43 196 967 905 3386 698 1429 677 1494 3261 187 1183 1903 3152 3071 3806 1799 3378 704 673 1763 372 346 117 1132 1648 1413 1063 2894 2624 263 2793 3956 2244 2723 4016 3161 3077 3877 1947 3686 522 2638 2713 2302 2235 4022 4062 3865 ...
output:
251799727
result:
ok single line: '251799727'
Subtask #8:
score: 1
Accepted
Test #64:
score: 1
Accepted
time: 965ms
memory: 101824kb
input:
4400 260 3770 2637 3654 540 2 3775 1444 1838 318 2500 1146 4325 1214 856 4283 4396 3031 299 330 3431 3019 452 1202 3265 3081 2550 3860 4137 4173 1766 1912 1487 3842 4163 3009 495 3503 3649 266 746 1096 836 394 225 2590 1039 1804 2025 2278 2519 2979 671 296 1704 4025 4113 2342 1192 4279 2234 3166 37 ...
output:
730836785
result:
ok single line: '730836785'
Test #65:
score: 0
Accepted
time: 947ms
memory: 101836kb
input:
4316 4128 221 1284 2189 2291 260 1873 3446 850 1769 30 3905 3773 2370 976 3417 2693 1183 429 2376 599 3325 737 2117 4382 2716 2486 1663 2712 4247 2617 2323 2492 3483 1326 211 3671 1768 2320 2982 983 3412 3838 965 3436 1400 1476 961 2254 1182 2425 3888 1120 1707 4164 2281 2927 4283 2587 2931 537 4313...
output:
300171766
result:
ok single line: '300171766'
Test #66:
score: 0
Accepted
time: 985ms
memory: 101784kb
input:
4372 3 738 3419 645 2572 878 185 2720 1396 2531 581 1979 402 4336 3670 4142 3203 1556 3992 3433 1513 634 3930 1295 1707 2605 2632 3192 448 1412 1187 3458 1539 386 2965 1411 252 3251 3793 2099 1417 2525 702 385 647 3992 3885 3620 3664 4045 3091 3994 1404 3733 2039 3864 264 2236 1718 4168 816 1312 333...
output:
872711060
result:
ok single line: '872711060'
Test #67:
score: 0
Accepted
time: 869ms
memory: 101860kb
input:
3930 402 2849 1485 2254 1533 1245 3994 1988 1205 1157 1912 2101 1865 2605 2994 675 729 3755 1533 1052 288 313 3432 2196 354 1286 1132 1002 2669 1452 3768 1560 3704 3982 3280 3944 2085 850 1077 1550 4126 2975 484 901 981 888 2940 1205 3564 4349 1991 2090 580 1091 2713 338 948 1872 2791 996 2418 994 3...
output:
240492525
result:
ok single line: '240492525'
Test #68:
score: 0
Accepted
time: 999ms
memory: 101800kb
input:
4379 295 4278 2705 49 299 3538 2882 1829 2882 4272 990 797 758 1700 83 2981 3052 1032 3617 205 3767 2777 4155 3801 2408 2438 136 1693 218 811 3354 4099 4128 945 3112 2865 841 1400 4371 3890 3966 2496 46 744 4144 3998 673 4396 1265 3535 3961 2994 1904 2072 2272 3783 1245 1643 3398 495 1132 3873 2068 ...
output:
581401227
result:
ok single line: '581401227'
Test #69:
score: 0
Accepted
time: 1006ms
memory: 101904kb
input:
4400 3549 2334 1746 2365 2438 2418 1590 4214 1492 2261 4397 2250 3016 1216 1250 1941 1983 1028 3857 3512 2392 613 2549 2624 200 2423 1709 1739 987 678 3962 110 680 3511 1859 1497 810 179 4009 2755 4173 4150 2776 3163 2783 1380 3990 802 2632 3403 1724 3613 1914 1247 1171 3036 3313 2315 2738 434 1057 ...
output:
846510244
result:
ok single line: '846510244'
Test #70:
score: 0
Accepted
time: 948ms
memory: 101884kb
input:
4283 2803 3636 1934 2963 4266 3776 2437 2122 2768 1951 1431 2213 253 1685 3748 79 3711 3633 4389 3724 1337 3283 3083 1103 2778 2446 3967 3708 1048 454 1477 3016 770 1888 611 600 3627 3439 1375 3310 1032 3407 3611 3003 823 1602 873 2815 1371 3968 228 1838 3610 3766 162 3072 2857 2444 72 3024 2838 735...
output:
896737922
result:
ok single line: '896737922'
Test #71:
score: 0
Accepted
time: 973ms
memory: 101824kb
input:
4400 840 723 4381 2702 4219 3749 2663 3763 1661 1685 2249 4020 2751 1721 101 1645 1820 1414 2387 179 171 3107 746 3808 1604 2298 1308 866 1315 119 353 3176 980 1089 3737 2257 852 2426 917 4004 2630 2089 1697 3243 3377 1969 3296 3176 1316 4027 2836 4387 269 1015 246 1812 779 936 2636 1952 1422 753 36...
output:
752816293
result:
ok single line: '752816293'
Test #72:
score: 0
Accepted
time: 962ms
memory: 101940kb
input:
4400 56 3557 2942 3003 372 2355 834 4357 3369 1076 4144 1052 2192 1579 3869 3441 3956 3846 1265 1773 3096 1949 1501 2318 562 1448 2766 1165 2421 3130 2239 309 2378 1141 3399 2944 3330 361 1636 3859 3196 967 52 2606 2098 2774 2783 440 103 152 294 997 853 1160 1100 2432 3452 1207 1758 71 923 3852 4184...
output:
27936228
result:
ok single line: '27936228'
Subtask #9:
score: 1
Accepted
Test #73:
score: 1
Accepted
time: 1082ms
memory: 102008kb
input:
4700 3056 4696 2025 918 614 2826 1716 4088 2833 3985 811 2428 1498 2827 1408 2121 4324 818 3281 4289 3931 1842 3071 4502 1410 3176 2098 3633 987 2942 3273 3338 3373 1868 976 4586 3537 2499 2 4477 383 560 2164 4542 4207 4279 586 327 3905 2363 4213 4460 1123 1314 763 1451 1437 4639 1268 4392 1516 4086...
output:
418991306
result:
ok single line: '418991306'
Test #74:
score: 0
Accepted
time: 1069ms
memory: 101948kb
input:
4591 949 638 1615 264 4648 3479 2143 1274 1498 2 2428 3316 232 32 2244 3284 581 1432 4252 4402 2202 806 4023 233 4093 2461 1538 630 1321 1739 1258 3627 4372 3711 910 4413 125 3567 4314 1260 3999 2765 4414 3634 2291 502 3461 3149 1868 2360 2662 4126 1054 4102 1596 1471 2403 2229 1649 2036 4261 3160 4...
output:
145199549
result:
ok single line: '145199549'
Test #75:
score: 0
Accepted
time: 1055ms
memory: 101812kb
input:
4661 372 3093 1877 1749 2869 3995 3640 3950 4481 726 2311 2704 1703 3000 2836 2810 825 3309 2067 4129 4564 152 2223 833 3748 4466 4482 645 115 53 575 3303 3768 3269 207 3169 4122 3300 3945 3745 2310 4464 1055 433 167 1541 4551 2366 761 1742 1008 849 3067 3271 239 4688 2141 3891 2165 3047 2841 4280 1...
output:
229187755
result:
ok single line: '229187755'
Test #76:
score: 0
Accepted
time: 1078ms
memory: 101880kb
input:
4700 3462 281 1676 2938 4448 2245 841 3184 3972 4071 1019 3027 3286 2371 1166 212 1868 3400 3486 3815 3324 3303 24 1919 2361 1510 1752 3992 3919 320 3186 1395 3424 1876 2425 2946 3764 3365 4303 4574 653 4272 2571 2981 885 2850 3538 3068 2699 3971 2959 1720 1691 852 935 3528 1901 996 583 1736 114 122...
output:
435552245
result:
ok single line: '435552245'
Test #77:
score: 0
Accepted
time: 1056ms
memory: 102008kb
input:
4695 4263 4590 2058 460 1163 1029 513 1165 3355 3057 4256 1681 393 3628 2240 4118 2101 1403 3978 470 991 3395 2649 1490 276 132 1303 1285 3121 4459 559 2364 4436 1552 2741 1839 3802 4683 1052 4334 430 2283 3519 486 544 2963 563 1075 1160 3244 167 3727 1441 1353 449 2683 34 3646 308 1657 1147 4038 41...
output:
42488545
result:
ok single line: '42488545'
Test #78:
score: 0
Accepted
time: 1073ms
memory: 101860kb
input:
4689 4471 4541 2821 160 4529 266 3118 1216 2584 25 1164 3241 970 2701 1543 936 3011 2766 3105 893 1730 1672 93 3420 1011 655 1693 2983 3194 2632 618 2624 1595 1956 63 287 4652 4128 710 433 2195 4242 3104 899 2131 50 642 3044 908 1611 2189 2576 1650 1371 420 2950 3363 3575 2686 4173 3284 1057 840 126...
output:
377840250
result:
ok single line: '377840250'
Test #79:
score: 0
Accepted
time: 1048ms
memory: 101876kb
input:
4699 4185 2051 4251 2028 558 3877 1547 7 4527 1718 2275 3421 2105 4661 3152 3738 4193 155 1817 741 2511 3875 4454 2092 440 2058 1212 3591 2797 3487 1902 3457 1593 4355 1172 1832 1340 2077 682 2460 3890 3063 2672 3460 1737 3233 3908 1366 4476 3636 158 1999 3010 3002 206 3940 3376 1452 769 359 3715 33...
output:
723865138
result:
ok single line: '723865138'
Test #80:
score: 0
Accepted
time: 1081ms
memory: 101952kb
input:
4700 373 1909 4575 2602 3909 4411 177 3748 1439 662 2517 1734 4036 893 1112 2833 721 2330 989 4075 2975 4022 4491 696 657 113 3191 2749 655 1752 1362 2279 977 4271 3121 2661 2848 1567 4159 1109 132 4550 4013 3984 739 2340 4048 2979 2940 3879 2150 4451 2643 3886 2405 2859 4358 354 2530 1393 3796 4622...
output:
113814916
result:
ok single line: '113814916'
Test #81:
score: 0
Accepted
time: 1056ms
memory: 101932kb
input:
4700 3403 306 303 3723 3040 3453 2127 3631 4176 2449 2784 2841 1242 4694 1121 231 4304 2433 3840 3055 4265 1015 4603 4129 8 281 3036 2130 2056 2096 2991 2021 515 4398 2592 255 3003 3491 4581 1422 646 1282 3051 309 3161 3921 4699 2921 1946 4122 4679 3091 4233 2490 523 2810 2136 2263 4589 3983 867 277...
output:
672513233
result:
ok single line: '672513233'
Subtask #10:
score: 0
Time Limit Exceeded
Test #82:
score: 1
Accepted
time: 1136ms
memory: 101944kb
input:
5000 4147 226 2474 4662 2345 2615 1968 2849 422 784 2041 3683 4926 850 3089 2033 2149 4446 2279 836 3286 1170 2724 2804 1745 2310 234 90 2671 3299 2733 1543 3544 3330 3473 31 2648 34 4607 4948 3106 1136 977 76 2899 4245 966 51 2567 2609 3166 2195 3273 2450 5000 4147 955 1011 2346 800 4413 3556 1118 ...
output:
245175451
result:
ok single line: '245175451'
Test #83:
score: 0
Accepted
time: 1157ms
memory: 101944kb
input:
4999 1246 4024 2029 567 1073 1306 3902 3386 3289 3304 2800 4502 3645 4582 487 4483 1031 1724 4941 3263 573 3244 2965 3352 4647 4556 4421 1577 1526 2648 4107 1256 2460 658 1886 2065 1751 496 2708 3940 2704 4701 2895 1656 1632 1915 2132 2930 2038 2752 1945 1372 1446 2411 6 1887 2248 1650 647 1055 2089...
output:
592893072
result:
ok single line: '592893072'
Test #84:
score: 0
Accepted
time: 1184ms
memory: 101896kb
input:
4998 4546 4587 2932 2915 3442 1627 690 4765 1334 1047 1704 767 5000 3259 4317 3099 1864 3003 1161 3390 2581 55 3710 1904 1591 1234 3677 4241 1629 2287 1294 3054 686 269 3443 1070 2699 2625 527 349 926 3951 1554 2693 46 4126 2870 3342 1483 2752 1843 2899 2039 2782 2070 2769 946 4601 2697 3900 3008 88...
output:
675710011
result:
ok single line: '675710011'
Test #85:
score: 0
Accepted
time: 1167ms
memory: 101824kb
input:
4997 3888 2103 3752 4876 3838 3640 4603 311 3572 1365 542 1055 1984 4445 1481 2210 3510 1959 3077 3870 4248 804 1907 3408 1379 180 827 206 644 1554 3135 2938 1651 2356 746 1886 2231 4782 4255 2714 264 1923 3723 398 90 226 1638 2228 2874 552 4759 1847 4273 1381 1603 3517 1964 1745 2905 182 3148 2329 ...
output:
535788092
result:
ok single line: '535788092'
Test #86:
score: 0
Accepted
time: 1167ms
memory: 101840kb
input:
4996 4580 1449 1090 548 943 3624 1408 1777 749 3029 4513 4477 1352 601 4084 2012 3685 3363 3164 3104 890 4981 3200 4172 3514 3712 2717 4158 2798 4041 3870 1490 3009 652 92 3737 4984 1657 4700 2486 2734 1440 959 2219 3886 4875 4720 584 3766 4114 391 604 2117 4306 2000 3685 4348 2371 3402 1178 1318 61...
output:
348044855
result:
ok single line: '348044855'
Test #87:
score: 0
Accepted
time: 1173ms
memory: 102008kb
input:
5000 2582 4813 3908 1948 3548 150 4913 1934 1243 4161 551 1515 2960 167 2351 3651 3766 76 1227 4279 149 4423 950 4650 534 4356 677 3685 1648 1142 846 51 1208 4615 1338 649 810 169 122 3038 694 3656 3251 2776 1389 1288 3830 4947 4837 767 1278 1638 629 3944 3925 707 3900 4312 4434 4276 469 4893 2502 3...
output:
513325548
result:
ok single line: '513325548'
Test #88:
score: 0
Accepted
time: 1301ms
memory: 101832kb
input:
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...
output:
104695471
result:
ok single line: '104695471'
Test #89:
score: 0
Accepted
time: 1200ms
memory: 102008kb
input:
5000 5000 5000 5000 4999 4999 4999 5000 5000 4999 4999 4999 5000 5000 5000 5000 5000 5000 5000 5000 4999 5000 5000 5000 4999 5000 4999 5000 5000 5000 5000 5000 5000 5000 4999 5000 5000 4999 5000 5000 4999 4999 4999 4999 5000 5000 5000 4999 4999 5000 4999 4999 5000 4999 4999 5000 4999 4999 5000 5000 ...
output:
836542551
result:
ok single line: '836542551'
Test #90:
score: 0
Accepted
time: 1157ms
memory: 101940kb
input:
5000 4991 4991 5000 4998 4998 4991 4995 4993 4995 4993 4991 4995 4992 5000 4994 5000 5000 4991 4999 4995 4991 4998 4994 4993 4992 4999 4991 4998 4993 4997 4997 4998 4998 4995 4995 4996 4998 4997 4992 4993 4996 4994 4999 4994 4999 4991 4997 4992 4993 4992 4992 4996 5000 4991 5000 4997 4999 4992 4993 ...
output:
871881558
result:
ok single line: '871881558'
Test #91:
score: -1
Time Limit Exceeded
input:
2000 1864 3721 2474 2221 1982 1579 674 2111 4846 2566 4798 971 2798 1948 2588 4426 991 2551 1996 4846 3098 4357 1306 1622 2503 547 1744 3931 2566 2599 2474 3701 4447 1762 368 2693 16 64 1762 3544 2311 3524 3904 2599 122 3214 2389 4421 1403 3067 3511 3118 3319 2048 4523 1583 3244 3779 1762 886 4568 1...