QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#618312 | #7185. Poor Students | Godzilla | AC ✓ | 155ms | 30844kb | C++14 | 3.2kb | 2024-10-06 20:52:55 | 2024-10-06 20:52:56 |
Judging History
answer
#include <bits/stdc++.h>
#define file_in(x) (freopen(#x".in", "r", stdin))
#define file_out(x) (freopen(#x".out", "w", stdout))
#define int long long
#define ull unsigned long long
#define vi vector
#define pb push_back
#define db long double
#define pr pair <int, int>
#define mk make_pair
#define fi first
#define se second
#define lb(x) (x & (-x))
using namespace std;
char _c; bool _f; template <class T> void IN(T &x) {
_f = x = 0; while (_c = getchar(), !isdigit(_c)) {if (_c == '-') _f = 1;}
while (isdigit(_c)) {x = x * 10 + _c - '0', _c = getchar();} if (_f) x = -x;
}
template <class T> void _write(T x) {
if (x < 0) return putchar('-'), _write(-x), void();
if (x > 9) _write(x / 10);
putchar('0' + x % 10);
}
template <class T> void write(T x) {_write(x), putchar('\n');}
template <class T> void write_s(T x) {_write(x), putchar(' ');}
template <class first, class... rest> void write(first fir, rest... res) {
write_s(fir), write(res...);
}
#define debug(...) (_debug(#__VA_ARGS__, __VA_ARGS__))
template <class T> void _debug(const char *format, T x) {
cerr << format << " = " << x << endl;
}
template <class first, class... rest>
void _debug(const char *format, first fir, rest... res) {
while (*format != ',') cerr << *format++;
cerr << " = " << fir << ',', _debug(format + 1, res...);
}
bool START;
const int N = 5e4 + 5, M = 15, inf = 1e14;
int n, K, c[N][M], mtc[N], dis[M], d[M][M], pre[M], ans, a[N];
bool vis[M];
queue <int> q;
struct heap {
priority_queue <pr, vi <pr>, greater <pr> > q;
void push(pr t) {q.push(t);}
void pop(int t = 0) {
while (!q.empty() && mtc[q.top().se] != t) q.pop();
}
pr top() {
if (q.empty()) return mk(-1, -1);
return q.top();
}
} f[M][M], g[M];
bool END;
void spfa(int n) {
while (!q.empty()) {
int x = q.front(); q.pop();
vis[x] = 0;
for (int y = 1; y <= n; ++y)
if (dis[x] + d[x][y] < dis[y]) {
dis[y] = dis[x] + d[x][y], pre[y] = x;
if (!vis[y]) vis[y] = 1, q.push(y);
}
}
}
signed main() {
//仔细检查,边界,特殊情况 ! ! !
cerr << (&END - &START) / 1024.0 / 1024.0 << endl;
IN(n), IN(K);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= K; ++j)
IN(c[i][j]), g[j].push(mk(c[i][j], i));
for (int i = 1; i <= K; ++i) IN(a[i]);
int num = n;
while (num--) {
for (int i = 0; i <= K; ++i) dis[i] = inf, vis[i] = pre[i] = 0;
for (int i = 0; i <= K; ++i) for (int j = 0; j <= K; ++j) d[i][j] = inf;
while (!q.empty()) q.pop();
for (int i = 1; i <= K; ++i) {
g[i].pop();
if (g[i].top().se != -1) dis[i] = g[i].top().fi, vis[i] = 1, q.push(i);
}
for (int i = 1; i <= K; ++i)
for (int j = 1; j <= K; ++j)
if (i != j) {
f[i][j].pop(i);
if (f[i][j].top().se != -1)
d[i][j] = f[i][j].top().fi;
}
spfa(K);
int p = 0; dis[0] = inf;
for (int i = 1; i <= K; ++i) if (a[i] && dis[i] < dis[p]) p = i;
a[p]--, ans += dis[p];
while (p) {
int x = pre[p], y = x ? f[x][p].top().se : g[p].top().se;
mtc[y] = p;
for (int i = 1; i <= K; ++i)
if (i != p)
f[p][i].push(mk(c[y][i] - c[y][p], y));
p = x;
}
}
write(ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
6 2 1 2 1 3 1 4 1 5 1 6 1 7 3 4
output:
12
result:
ok answer is '12'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5844kb
input:
3 3 1 2 3 2 4 6 6 5 4 1 1 1
output:
8
result:
ok answer is '8'
Test #3:
score: 0
Accepted
time: 2ms
memory: 4292kb
input:
1000 10 734 303 991 681 755 155 300 483 702 442 237 256 299 675 671 757 112 853 759 233 979 340 288 377 718 199 935 666 576 842 537 363 592 349 494 961 864 727 84 813 340 78 600 492 118 421 478 925 552 617 517 589 716 7 928 638 258 297 706 787 266 746 913 978 436 859 701 951 137 44 815 336 471 720 2...
output:
92039
result:
ok answer is '92039'
Test #4:
score: 0
Accepted
time: 10ms
memory: 6376kb
input:
5000 10 14 114 254 832 38 904 25 147 998 785 917 694 750 372 379 887 247 817 999 117 802 15 799 515 316 42 69 247 95 144 727 398 509 725 682 456 369 656 693 955 923 1 681 631 962 826 233 963 289 856 165 491 488 832 111 950 853 791 929 240 509 843 667 970 469 260 447 477 161 431 514 903 627 236 144 3...
output:
461878
result:
ok answer is '461878'
Test #5:
score: 0
Accepted
time: 20ms
memory: 9548kb
input:
10000 10 307 205 765 487 504 526 10 581 234 583 448 443 39 992 976 363 335 588 588 169 920 787 896 822 47 358 230 631 136 299 141 159 414 852 922 945 513 76 111 189 616 104 83 792 24 68 164 975 615 472 150 108 848 517 7 153 107 283 452 165 94 370 910 662 226 720 975 214 324 407 636 65 963 859 590 3 ...
output:
919745
result:
ok answer is '919745'
Test #6:
score: 0
Accepted
time: 97ms
memory: 27776kb
input:
50000 10 819 49 278 985 747 872 146 129 898 569 929 427 54 846 136 475 448 304 591 428 238 844 664 991 990 863 308 571 867 958 775 690 792 697 557 325 824 654 303 833 542 942 262 534 501 575 273 60 701 488 733 855 810 405 294 909 638 975 801 836 382 265 818 765 240 69 980 889 472 211 629 434 128 389...
output:
4558242
result:
ok answer is '4558242'
Test #7:
score: 0
Accepted
time: 105ms
memory: 27700kb
input:
50000 10 381 642 238 598 634 432 828 277 275 239 963 771 114 457 411 717 85 260 527 664 138 832 923 332 197 371 30 412 47 568 266 38 327 563 564 14 943 698 881 747 627 788 567 438 371 524 490 674 809 839 322 680 178 515 376 355 928 880 827 446 702 107 650 811 360 226 283 138 357 489 121 364 656 377 ...
output:
4595976
result:
ok answer is '4595976'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5852kb
input:
5 3 2 4 5 5 9 9 2 7 9 4 2 2 4 1 7 3 3 3
output:
12
result:
ok answer is '12'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5852kb
input:
10 7 1 9 9 3 5 5 7 6 1 6 3 4 3 6 9 6 8 5 5 2 7 3 8 8 6 6 6 3 5 8 1 9 7 9 5 3 2 3 7 7 8 7 4 1 2 3 3 3 7 8 1 7 3 4 2 7 7 1 1 9 2 7 3 4 9 8 9 6 8 9 10 2 1 1 2 1 1
output:
21
result:
ok answer is '21'
Test #10:
score: 0
Accepted
time: 9ms
memory: 7328kb
input:
10000 7 6 5 9 8 5 5 5 2 4 5 2 7 8 9 7 3 7 2 6 8 8 8 1 6 4 8 6 9 2 3 8 1 3 5 5 1 5 6 1 3 1 6 2 7 7 3 5 9 5 1 9 9 6 8 5 5 1 4 2 4 6 7 7 8 4 1 5 2 2 1 7 9 9 5 5 1 2 9 7 1 3 9 5 9 6 7 3 6 3 8 3 7 7 2 4 2 4 5 5 5 9 8 2 4 9 9 5 8 4 7 2 9 4 3 4 8 4 3 3 8 3 7 9 6 6 6 5 4 5 2 6 3 9 4 9 5 6 1 3 2 4 1 2 6 6 5 ...
output:
44137
result:
ok answer is '44137'
Test #11:
score: 0
Accepted
time: 9ms
memory: 8520kb
input:
10000 6 3 4 1 4 5 4 4 4 3 7 7 2 6 6 8 1 9 9 2 5 5 1 7 3 9 7 7 3 3 8 5 7 1 2 6 3 2 8 9 4 9 1 4 8 3 2 1 7 4 9 2 3 8 5 1 6 2 2 9 1 1 4 9 8 9 6 3 8 3 7 6 1 3 1 5 7 9 5 5 3 8 1 2 8 5 1 8 3 9 4 1 5 4 5 5 4 9 4 1 8 8 4 5 6 7 5 8 2 3 1 6 2 3 1 2 7 4 8 5 6 5 4 3 2 5 1 8 5 4 7 3 2 7 5 2 3 1 1 3 1 1 7 3 1 2 6 ...
output:
21143
result:
ok answer is '21143'
Test #12:
score: 0
Accepted
time: 10ms
memory: 7920kb
input:
10000 6 26621560 22574851 99124663 42644108 73831692 34062679 10875678 33632518 99379217 52587402 68258572 82863 6133022 1452838 27530175 15603746 10928055 64045100 4919237 15636901 89763 37033224 76358345 23420261 87262364 92257115 7193645 40262131 78897499 70538741 45451167 2937593 39330094 300263...
output:
176215561116
result:
ok answer is '176215561116'
Test #13:
score: 0
Accepted
time: 14ms
memory: 8144kb
input:
10000 6 505488678 436228096 333558553 129070925 123808864 36937787 503324046 79831519 80269630 548781256 374673233 280839716 209008459 554326459 255308141 256669834 530478297 51026940 351489261 459988802 392737197 83890293 359338753 331620684 201060883 194683095 375867041 232603637 138654087 1929412...
output:
1034670171939
result:
ok answer is '1034670171939'
Test #14:
score: 0
Accepted
time: 14ms
memory: 9072kb
input:
10000 6 89916134 29433813 59399087 464898320 558107935 422188143 547054926 559929858 728302681 5219270 834478116 259909510 816488311 368359373 194676880 330286055 245200722 87979527 63366579 585173909 706460949 49644677 770070184 329255152 314412303 288716719 333799370 614570900 406350296 696208263 ...
output:
1773428571657
result:
ok answer is '1773428571657'
Test #15:
score: 0
Accepted
time: 8ms
memory: 8752kb
input:
10000 6 66237379 181806248 509510118 323698055 917981861 381020346 891370175 602465447 651904218 27588579 475265754 430666261 874613865 991962519 265069683 393546179 987679666 717041057 675429255 645133077 623980032 953549198 946201757 765785432 954715369 623518217 681467056 740740198 415802185 5827...
output:
1439875611641
result:
ok answer is '1439875611641'
Test #16:
score: 0
Accepted
time: 13ms
memory: 8124kb
input:
10000 6 109501946 925691998 114115135 829446594 173795627 891153669 264844500 481537403 422647594 964796147 386517450 581623444 921172582 375091327 237314301 608361127 357677517 595119843 119651751 659029470 938251974 210093064 369958476 821941442 411555569 328723790 979811779 137795697 512892726 39...
output:
1561994475072
result:
ok answer is '1561994475072'
Test #17:
score: 0
Accepted
time: 13ms
memory: 7840kb
input:
10000 6 214242852 862344228 444719752 969065314 468060368 232241544 786803413 801480781 666280058 298466884 28589081 984412665 436101075 178002287 220595950 936235752 308790537 65171840 853973125 4091452 854764838 888615836 554917488 238207448 499378894 673682464 358195819 455995859 52657992 5920135...
output:
1444521827648
result:
ok answer is '1444521827648'
Test #18:
score: 0
Accepted
time: 20ms
memory: 12568kb
input:
50000 2 3 8 8 3 4 9 4 7 6 6 9 1 5 6 2 1 8 6 4 1 2 5 2 7 8 4 1 9 2 6 6 5 9 8 2 2 8 8 4 1 3 2 5 8 9 7 5 4 8 6 9 4 3 8 7 3 4 3 6 4 1 1 5 5 1 6 2 8 8 1 3 2 7 6 3 7 5 2 6 3 6 2 1 2 1 4 3 2 8 1 9 4 4 8 6 9 5 7 4 2 5 1 1 7 4 9 9 9 4 3 4 1 9 9 1 4 7 5 7 2 5 1 3 2 7 7 6 7 7 9 1 2 9 1 5 2 7 6 9 9 3 4 9 6 8 4 ...
output:
176124
result:
ok answer is '176124'
Test #19:
score: 0
Accepted
time: 20ms
memory: 12668kb
input:
50000 2 7 8 7 2 1 7 4 7 9 3 9 5 6 7 9 5 6 5 5 9 2 8 7 2 1 1 3 6 5 1 6 1 3 4 4 3 7 4 5 7 8 6 4 2 7 7 7 6 3 1 2 6 5 5 4 7 2 2 6 7 4 7 7 7 6 5 5 1 7 6 7 1 4 9 3 4 8 9 1 2 4 5 6 7 5 1 6 9 7 8 7 3 3 2 2 6 6 5 1 1 7 5 6 5 8 4 6 1 9 2 6 3 2 8 9 2 9 2 4 1 6 5 8 7 3 4 2 2 9 5 4 4 8 9 8 1 9 5 5 7 6 7 8 6 8 8 ...
output:
177533
result:
ok answer is '177533'
Test #20:
score: 0
Accepted
time: 111ms
memory: 30844kb
input:
50000 10 1824 2363 5240 1212 3128 7792 4378 6737 6873 4561 6684 2808 5841 7269 1104 3757 7 9932 9632 4854 9932 4447 2965 3922 7850 6872 2608 9167 1883 5406 4782 7230 3002 8699 1262 2250 7887 4108 3047 4316 7201 9791 1853 6276 3058 7801 9499 1955 1574 772 5864 9874 1922 7714 9288 7860 1638 1972 1656 ...
output:
97744364
result:
ok answer is '97744364'
Test #21:
score: 0
Accepted
time: 118ms
memory: 27704kb
input:
50000 10 2805 3778 5335 84 1469 5531 8230 3676 9657 9550 7655 7925 1349 2743 9386 5272 5208 2769 222 8429 1441 5456 9320 5457 2254 6681 9525 6966 7646 2514 1106 2451 4523 1117 1452 5136 940 8349 4325 2506 7565 6257 6307 7785 1758 3084 7702 7174 6598 7917 2295 5399 2630 7826 5276 2830 7127 3433 630 1...
output:
47609008
result:
ok answer is '47609008'
Test #22:
score: 0
Accepted
time: 113ms
memory: 27276kb
input:
50000 10 4945 8281 7207 7498 3135 8902 3753 327 6931 5403 6843 5658 677 1566 9115 1116 364 8522 779 3707 6088 9697 79 2726 2110 9645 989 8787 2103 2703 3400 1962 340 3137 893 9996 5450 5835 7875 8223 5758 1518 630 3244 9952 1634 3541 4997 9420 1849 6417 1897 6413 5377 4786 8664 9382 5744 712 7626 12...
output:
48029932
result:
ok answer is '48029932'
Test #23:
score: 0
Accepted
time: 106ms
memory: 27608kb
input:
50000 10 8529 6814 3851 4143 3281 5256 2152 4151 6603 1490 596 5776 2024 2601 8258 5037 9756 7162 3910 5345 2901 3606 8604 7462 4615 8766 7644 1766 6005 7156 3448 3495 8566 5637 6960 584 5808 8731 2487 1587 3713 6662 6804 3305 5368 6442 5711 9987 3312 5151 7534 6034 257 6354 242 153 1360 484 1661 40...
output:
47775092
result:
ok answer is '47775092'
Test #24:
score: 0
Accepted
time: 106ms
memory: 27328kb
input:
50000 10 9682 8540 9492 7313 2454 4895 3643 1211 8946 1585 7855 4409 2505 5409 2345 7514 6159 1886 9560 3269 4954 5885 4932 4971 2250 9970 196 6165 619 7168 3846 486 5876 1308 3852 3602 7292 8837 565 1949 9568 5610 3776 613 6981 1203 9620 8008 1297 985 5454 1611 1535 8118 2584 5499 5665 8593 9884 15...
output:
47895396
result:
ok answer is '47895396'
Test #25:
score: 0
Accepted
time: 101ms
memory: 27864kb
input:
50000 10 6315 1094 894 7236 9575 6742 8643 2222 5263 5134 8928 5850 2780 8036 5217 3974 3627 6242 2413 7632 9825 7173 796 4751 3519 7903 8846 7614 3191 226 3610 1474 6537 5242 6730 4646 607 6436 3100 7641 8242 2270 5848 2927 5187 2638 479 5104 6901 4498 4149 805 858 7173 1808 6254 8207 8165 3086 195...
output:
45828764
result:
ok answer is '45828764'
Test #26:
score: 0
Accepted
time: 107ms
memory: 27932kb
input:
50000 10 1229 2898 2885 4865 6967 4324 500 9786 2817 6978 8202 9199 5946 5254 3333 3481 2890 3283 3986 4275 3786 4058 2787 352 8245 7036 652 2541 1064 9755 1663 4816 6843 5152 4725 8980 9082 4721 4774 1961 5037 71 7875 9461 7575 3314 9465 1973 1343 9534 5794 1349 8338 2855 2041 2396 8642 546 8932 83...
output:
45736329
result:
ok answer is '45736329'
Test #27:
score: 0
Accepted
time: 119ms
memory: 26832kb
input:
50000 10 4991 9685 5723 8310 5162 7991 464 6415 1322 3335 9344 1092 9504 618 8107 3351 3112 5980 8207 5642 2055 8198 7808 6384 5241 3049 8681 4319 1536 6342 8037 9510 1057 9213 1670 2006 5192 9950 1286 3550 433 5598 4689 7502 8528 8901 175 8348 5080 8090 6633 2978 3979 2622 625 1146 3089 9429 5453 3...
output:
53803793
result:
ok answer is '53803793'
Test #28:
score: 0
Accepted
time: 155ms
memory: 26892kb
input:
50000 10 263 656 3591 2040 5059 2270 7622 5964 6749 5948 4162 70 158 9650 2122 6575 1502 5657 6210 6038 4713 1055 5829 529 9034 104 634 1607 3206 7265 4994 2527 7411 478 3170 6469 7429 7058 771 3917 7281 2429 4624 4186 6297 3407 2238 296 265 5263 2117 1809 6514 1616 9666 6464 2410 1384 1373 8286 545...
output:
50558646
result:
ok answer is '50558646'
Test #29:
score: 0
Accepted
time: 139ms
memory: 27916kb
input:
50000 10 680 2925 5108 5577 2822 1996 3730 9647 7399 8687 7313 3213 9023 5630 2334 7289 9086 9325 8365 9689 1309 4675 9888 9178 3206 142 7170 5693 5800 9625 2605 2567 9968 4546 2536 1068 1321 6574 3020 8794 7616 7586 2993 8538 439 5218 6931 7176 2081 9802 6890 9158 7006 1873 2829 4993 7479 5303 6862...
output:
45229804
result:
ok answer is '45229804'
Test #30:
score: 0
Accepted
time: 121ms
memory: 27612kb
input:
50000 10 3074 2857 3294 4431 4370 8319 547 4845 5048 4999 3655 8903 1933 7601 7526 8563 8970 3670 7905 8003 8826 8566 8148 6835 3515 6643 7 6476 5572 4712 801 576 2340 7154 3373 9212 3757 9020 1176 9520 4267 6001 5775 423 932 5956 1473 5602 5438 4260 6 7166 1406 8728 3695 3187 971 7430 7331 7781 614...
output:
45312529
result:
ok answer is '45312529'
Test #31:
score: 0
Accepted
time: 119ms
memory: 27616kb
input:
50000 10 5467 2789 3062 3284 7499 3060 7363 1625 4278 1310 8415 4593 3259 7990 2720 8255 8855 8014 7445 6317 4762 2457 4827 4492 3825 4726 4426 7260 6925 8215 8996 8583 6292 9762 5791 8938 6192 3049 7750 248 9335 2834 8557 2307 9842 6694 4432 4029 8795 301 3122 6756 5804 4003 4562 9799 6044 1141 621...
output:
45456618
result:
ok answer is '45456618'
Test #32:
score: 0
Accepted
time: 121ms
memory: 27816kb
input:
50000 10 3852 3910 6453 6900 6508 5019 2082 1809 6259 9731 8387 6909 7753 5836 5327 4534 6798 5644 9002 6443 8907 153 9181 5627 7240 4337 621 2629 1961 9766 9792 1028 9843 8015 4311 1823 9318 8173 6917 9831 6535 1197 1850 6857 8688 7270 5455 223 4911 4826 1342 7306 1554 551 4254 5557 1712 8649 9136 ...
output:
45328645
result:
ok answer is '45328645'
Test #33:
score: 0
Accepted
time: 108ms
memory: 27688kb
input:
50000 10 5911 2041 3972 1678 6278 7712 1178 9746 7745 1624 8966 8591 2535 5523 9403 1674 4538 3309 9919 4964 8532 1170 2446 3593 6191 8405 939 2779 1292 5186 8432 5638 73 6188 9419 2281 3325 4049 7761 471 9741 555 7129 2388 4992 914 7428 6035 6267 4270 9476 3518 1536 4698 6632 8290 7804 7861 7552 34...
output:
45457443
result:
ok answer is '45457443'
Test #34:
score: 0
Accepted
time: 117ms
memory: 27700kb
input:
50000 10 76551321 42771251 50102295 39280938 45263454 79797046 10803054 45781565 77089368 91227654 80058111 7361931 74490827 87574706 49601805 87737654 35832951 29590101 53663591 33462640 22171056 57518634 47955581 40395087 31331896 51706118 50229887 68108693 6779469 18400895 1709708 82136753 887660...
output:
456114887126
result:
ok answer is '456114887126'
Test #35:
score: 0
Accepted
time: 118ms
memory: 28496kb
input:
50000 10 4330 9027 7145 71 8528 5890 6082 3462 8563 4617 5545 7238 6009 1677 1088 8637 6692 1329 3301 2856 4674 1804 7507 8905 8467 5816 6435 4954 8302 6939 5757 6212 1875 1766 2949 3425 6435 6804 4675 8362 4466 7436 2338 9021 9964 5122 407 5420 4006 8034 2933 3010 4403 4310 7602 840 9559 3975 6295 ...
output:
76544399
result:
ok answer is '76544399'
Test #36:
score: 0
Accepted
time: 114ms
memory: 28504kb
input:
50000 10 776 2211 5484 5959 5115 4627 4304 5723 9672 7936 689 5523 6730 8572 3675 7448 383 9202 8749 7960 2346 9927 6316 2650 5126 1942 5545 4333 6438 3919 7126 3597 4706 2010 9687 2492 4237 9944 5663 4051 2519 7049 3649 1168 5704 3605 4082 2049 3821 4965 4325 9463 2492 1457 8464 6164 7917 6512 8262...
output:
76249432
result:
ok answer is '76249432'
Extra Test:
score: 0
Extra Test Passed