QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#344357 | #4238. Zero Sum | Thienu | AC ✓ | 4994ms | 7300kb | C++20 | 2.9kb | 2024-03-04 09:05:21 | 2024-03-04 09:05:21 |
Judging History
answer
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
using uint = unsigned int;
using ull = unsigned long long;
template<typename C> struct rge{C l, r;};
template<typename C> rge<C> range(C i, C j) { return rge<C>{i, j}; }
template<typename C> ostream& operator<<(ostream &os, rge<C> &r) { os << '{'; for(auto it = r.l; it != r.r; it++) os << "," + (it == r.l) << *it; os << '}'; return os; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '{' << p.first << "," << p.second << '}'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ","; return os << '}'; }
void dbg_out() { cerr << ']' << endl; }
template<typename A> void dbg_out(A H) { cerr << H; dbg_out(); }
template<typename A, typename B, typename... C> void dbg_out(A H, B G, C... T) { cerr << H << ","; dbg_out(G, T...); }
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = [", dbg_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int N = 35005;
ll dp[2][3*N];
ll mat[N][7];
int BIL = 1'000'000'000;
const int K = 7;
#define d(p) dp[cur^1][j+p] = min(dp[cur^1][j+p], dp[cur][j] + mat[i][p]);
#define body(j) d(0) d(1) d(2) d(3) d(4) d(5) d(6) j++;
void solve(){
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++) {
for(int j = 0; j <= 2*k; j++) {
cin >> mat[i][j];
mat[i][j] -= 2 * BIL;
}
}
int cur = 0;
for(int i = 0; i < n; i++) {
memset(dp[cur^1], 0, sizeof(dp[cur^1]));
int llim = max(0, 2*k*i-n*k);
int rlim = min(n*k, 2*k*i);
int j = llim;
while((j & 15) && j <= rlim) {
body(j)
}
while(j + 16 <= rlim) {
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
body(j)
}
while(j <= rlim) {
body(j)
}
cur ^= 1;
}
cout << dp[cur][n*k] + (ll)2 * BIL * n << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5340kb
input:
3 1 3 14 15 -3 -5 -35 2 71 82
output:
-19
result:
ok 1 number(s): "-19"
Test #2:
score: 0
Accepted
time: 0ms
memory: 6024kb
input:
5 2 1 2 5 14 42 1 2 3 5 8 1 2 4 8 16 1 2 3 4 5 1 2 6 24 120
output:
16
result:
ok 1 number(s): "16"
Test #3:
score: 0
Accepted
time: 1ms
memory: 6388kb
input:
10 2 -904071845 760493887 -478285804 759035367 -680013382 -587322944 665345507 -20509293 103731947 864888628 738633646 936703855 -370523881 301151360 478433861 703775172 -913389861 691762973 -185132991 543994805 -511007159 118916858 891184 349354959 267412081 -663269925 14450557 369277951 237764429 ...
output:
-6259997315
result:
ok 1 number(s): "-6259997315"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5336kb
input:
10 2 -566639283 -281454349 687175663 817449090 928108928 -819788458 -442586076 -451652406 403601435 -168825683 -649266596 187412594 -856159947 476347172 20574258 -390470703 -791341926 -60895976 842388030 507828204 159048971 -531035734 -110061386 255061473 -622553675 767534638 296274618 318355641 -60...
output:
-5863402983
result:
ok 1 number(s): "-5863402983"
Test #5:
score: 0
Accepted
time: 3556ms
memory: 7172kb
input:
35000 2 -323024395 123746159 618869974 -455533063 294962647 9971372 784839881 -906564905 -578266269 944975915 968956358 -576765224 448197684 986539127 -525297570 -745293354 426913995 129954892 255813154 -243728523 -922616050 -983803120 -317189892 362753890 481320837 -626411581 760532893 481031139 14...
output:
-23326299571078
result:
ok 1 number(s): "-23326299571078"
Test #6:
score: 0
Accepted
time: 4981ms
memory: 7236kb
input:
35000 3 -389986454 -678028773 330282316 582141258 -976039033 415560778 -256794145 891726219 -744524869 671251658 67347457 -91229912 -787543984 364694820 606490044 511500731 766802212 79214055 -745406592 -843185684 -709300461 -806048178 750955329 92731052 -740911920 943335651 -961204999 72788590 5815...
output:
-26267884225753
result:
ok 1 number(s): "-26267884225753"
Test #7:
score: 0
Accepted
time: 4967ms
memory: 7232kb
input:
35000 3 -205476456 82285866 -35594070 0 53353652 -49927864 -111238731 113551347 -133551112 19375782 0 -89200221 121851958 207015309 57966468 -78468406 -89972877 0 -14958562 -153791584 207214716 41705397 -138035132 34758504 0 -91078140 3818342 -281759472 199952820 -173442272 -63649020 0 69365700 -761...
output:
-5671382440154
result:
ok 1 number(s): "-5671382440154"
Test #8:
score: 0
Accepted
time: 4970ms
memory: 7216kb
input:
35000 3 -104465988 -61243572 -85539391 0 7491458 10264978 124155243 -268558005 -154632718 -21620750 0 27153711 122054610 116554080 -37253310 -179203364 -12517155 0 24722702 80407004 66380241 -37560414 -147869008 -55350255 0 21547694 5632026 174871269 -209389992 -184668276 -34948820 0 9415470 8251568...
output:
-6078227814541
result:
ok 1 number(s): "-6078227814541"
Test #9:
score: 0
Accepted
time: 4968ms
memory: 7216kb
input:
35000 3 902444553 382219274 435764110 878892951 655614413 151116197 232298986 213739238 198177043 698942673 772039014 372652389 180586024 6396281 87942969 598386916 -49947342 39272933 968460479 949268130 968282113 738343828 95663007 635955539 -9208067 652112369 431840638 284151628 -58473132 30378755...
output:
-14462236943288
result:
ok 1 number(s): "-14462236943288"
Test #10:
score: 0
Accepted
time: 4978ms
memory: 7172kb
input:
35000 3 113961247 593708547 248864537 180118601 925518310 15254920 577036150 279961671 63364217 713049091 937580207 329002834 77859362 357285128 881748603 693652749 303956346 894180781 819899770 372981112 353387093 365389658 535559085 447104136 272739305 115939848 179347884 709464863 -99411860 39686...
output:
-636458673506
result:
ok 1 number(s): "-636458673506"
Test #11:
score: 0
Accepted
time: 4954ms
memory: 7248kb
input:
35000 3 671257145 87472903 647195116 960778581 327005775 269169516 123922983 284052436 853466191 395187549 872459399 961583162 671293207 31377460 162077596 758965589 964095767 356305312 941818506 841868937 18061159 929743495 443985166 961520354 537431927 982805255 484995037 848027892 352415069 16624...
output:
2382205891728
result:
ok 1 number(s): "2382205891728"
Test #12:
score: 0
Accepted
time: 4979ms
memory: 7160kb
input:
35000 3 286266440 749544229 845081932 986126225 704197478 357932327 320262234 902658169 983782929 248169641 394709844 753187053 797399106 340299748 503097699 845504290 694061174 426893618 549257450 280583394 156194149 639874747 779111479 478326212 760154985 621391283 900712823 131080194 202287918 82...
output:
7437279629050
result:
ok 1 number(s): "7437279629050"
Test #13:
score: 0
Accepted
time: 4963ms
memory: 7296kb
input:
35000 3 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -100...
output:
-35000000000000
result:
ok 1 number(s): "-35000000000000"
Test #14:
score: 0
Accepted
time: 4974ms
memory: 7172kb
input:
35000 3 -214231740 561828360 76241266 472660258 242381160 463748494 755426285 -338249027 670482502 925122567 34876129 665851249 806877747 763800269 -645259236 835667403 720749523 533537248 -631174 208763832 285452509 -247662789 453838584 609124240 906898701 373237786 808969422 11914645 -432735167 53...
output:
-17515051871501
result:
ok 1 number(s): "-17515051871501"
Test #15:
score: 0
Accepted
time: 4969ms
memory: 7228kb
input:
35000 3 20794357 456880162 290004769 -9549730 837821291 496673594 191928369 846990684 -333159656 971566129 30393254 307216470 471344754 505250909 449549169 73610804 273558221 -502868308 797185424 513477788 924836911 960502857 -243276990 939475100 -4162937 192976290 304856124 274231878 9306519 636404...
output:
-17382024534479
result:
ok 1 number(s): "-17382024534479"
Test #16:
score: 0
Accepted
time: 4946ms
memory: 7268kb
input:
35000 3 -343986352 365994591 733454454 88241130 686200086 649287462 451956415 862680531 114371590 -687859475 161945421 904845732 475553530 830716450 925756868 394957191 739654554 -595366187 228280993 663141658 619236347 -813199062 656969440 624546708 694716268 901691045 72252672 360859331 -755150515...
output:
-16386303904972
result:
ok 1 number(s): "-16386303904972"
Test #17:
score: 0
Accepted
time: 4961ms
memory: 7300kb
input:
35000 3 16376630 636920797 -747011125 251356580 991450540 10250736 755965469 -754695295 854417641 898311615 819053951 285891263 883305185 719914650 -186930138 926199485 682399764 409243588 491836896 786333955 34188957 233154646 146016100 -298477569 579201592 134269725 74386754 -1151228 399624830 674...
output:
-13433828357291
result:
ok 1 number(s): "-13433828357291"
Test #18:
score: 0
Accepted
time: 4950ms
memory: 7296kb
input:
35000 3 838627654 725783378 599972392 -523911293 173524472 694625507 -2005222 685254059 8058524 666820714 -513255094 159679521 665019678 689428405 156785487 -403637015 197931854 818898612 139540082 419692725 754453116 6368399 1600421 8584740 889761078 699967086 773496509 426437174 998890018 93313742...
output:
-14168146410214
result:
ok 1 number(s): "-14168146410214"
Test #19:
score: 0
Accepted
time: 4980ms
memory: 7172kb
input:
35000 3 507082600 285689379 61868963 -672344747 919417931 100471198 769224659 202694139 -633883041 146067549 236977539 866786392 992854494 412574154 197760795 843355561 39952436 -635033407 590455708 555983768 425305837 610549308 150411589 -249845191 208084775 281628859 397691815 571325862 506444556 ...
output:
-16023734295663
result:
ok 1 number(s): "-16023734295663"
Test #20:
score: 0
Accepted
time: 4969ms
memory: 7232kb
input:
35000 3 998679821 280141604 -331037900 545053730 384806779 -6595381 746645457 395002703 -733266870 648564987 907380271 221074556 713362749 46220413 145920886 -736282063 817587535 168526038 50044889 643230764 649747029 730499129 -360289859 500337327 62551737 847369202 712102198 253685535 -600624208 9...
output:
-17033520309396
result:
ok 1 number(s): "-17033520309396"
Test #21:
score: 0
Accepted
time: 4940ms
memory: 7172kb
input:
35000 3 266450531 997280342 -826722239 20961271 484446099 756834975 330333309 86019739 210378748 737640154 -317403259 -4165681 566389396 550919451 798777001 7580986 -273244628 219171008 661908661 800149358 109537633 -440890231 406596014 230102304 475268870 622759482 557656439 257035518 593323383 889...
output:
-13012929921312
result:
ok 1 number(s): "-13012929921312"
Test #22:
score: 0
Accepted
time: 4961ms
memory: 7172kb
input:
35000 3 -889322248 101499700 710082363 653650024 779296985 466783728 980586628 223810434 103682331 678341816 -178564107 411904871 662968137 432745789 -508617339 794543797 855540371 281415828 465186021 721034538 62219693 876170334 -11016489 505312000 561475965 24070151 838124708 544774620 -687343840 ...
output:
-12562859517099
result:
ok 1 number(s): "-12562859517099"
Test #23:
score: 0
Accepted
time: 4976ms
memory: 7172kb
input:
35000 3 386125179 -43074427 229515027 -242735485 366066634 945429565 685073611 533628879 -512918068 985896519 88621976 631015731 528072235 463547925 4185707 389501534 233744658 -73660284 988146766 558510686 238123280 667106675 307156960 -104192132 299852054 972649164 589367909 -55931607 63826763 668...
output:
-15907025267713
result:
ok 1 number(s): "-15907025267713"
Test #24:
score: 0
Accepted
time: 4994ms
memory: 7284kb
input:
35000 3 874133382 -46118008 -967872888 28430409 437264729 580051990 808942458 580289587 598325404 238993913 -966206946 679513216 264303895 280806135 -269493748 771960670 198673149 298535587 -19255688 956682433 58152589 301073461 821846165 -899346404 447699820 304648609 112941867 701957565 240406387 ...
output:
-14314485699924
result:
ok 1 number(s): "-14314485699924"
Test #25:
score: 0
Accepted
time: 4954ms
memory: 7244kb
input:
35000 3 54030005 695002288 566899973 -916692266 214724271 281816450 813239673 533728654 796474206 840220631 70388155 315692234 81228958 471474297 -666200856 196209502 124313223 288346181 336616252 248108793 184081192 -173390418 480767342 643401943 59660889 327053560 300518413 100803794 803859998 -75...
output:
-15060410292461
result:
ok 1 number(s): "-15060410292461"