QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178375#1225. 序列hos_lyric100 ✓448ms25644kbC++148.2kb2023-09-13 21:54:292023-09-13 21:54:30

Judging History

你现在查看的是最新测评结果

  • [2023-09-13 21:54:30]
  • 评测
  • 测评结果:100
  • 用时:448ms
  • 内存:25644kb
  • [2023-09-13 21:54:29]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// Minimum cost flow by successive shortest paths.
// Assumes that there exists no negative-cost cycle.
// TODO: Check the range of intermediate values.
template <class Flow, class Cost> struct MinCostFlow {
  // Watch out when using types other than int and long long.
  static constexpr Flow FLOW_EPS = 1e-10L;
  static constexpr Flow FLOW_INF = std::numeric_limits<Flow>::max();
  static constexpr Cost COST_EPS = 1e-10L;
  static constexpr Cost COST_INF = std::numeric_limits<Cost>::max();

  int n, m;
  vector<int> ptr, nxt, zu;
  vector<Flow> capa;
  vector<Cost> cost;

  explicit MinCostFlow(int n_) : n(n_), m(0), ptr(n_, -1) {}
  void ae(int u, int v, Flow w, Cost c) {
    assert(0 <= u); assert(u < n);
    assert(0 <= v); assert(v < n);
    assert(0 <= w);
    nxt.push_back(ptr[u]); zu.push_back(v); capa.push_back(w); cost.push_back( c); ptr[u] = m++;
    nxt.push_back(ptr[v]); zu.push_back(u); capa.push_back(0); cost.push_back(-c); ptr[v] = m++;
  }

  vector<Cost> pot, dist;
  vector<bool> vis;
  vector<int> pari;

  // cost slopes[j] per flow when flows[j] <= flow <= flows[j + 1]
  vector<Flow> flows;
  vector<Cost> slopes;

  // Finds a shortest path from s to t in the residual graph.
  // O((n + m) log m) time.
  //   Assumes that the members above are set.
  //   The distance to a vertex might not be determined if it is >= dist[t].
  //   You can pass t = -1 to find a shortest path to each vertex.
  void shortest(int s, int t) {
    using Entry = pair<Cost, int>;
    priority_queue<Entry, vector<Entry>, std::greater<Entry>> que;
    for (int u = 0; u < n; ++u) { dist[u] = COST_INF; vis[u] = false; }
    for (que.emplace(dist[s] = 0, s); !que.empty(); ) {
      const Cost c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (vis[u]) continue;
      vis[u] = true;
      if (u == t) return;
      for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > FLOW_EPS) {
        const int v = zu[i];
        if (!vis[v]) {
          const Cost cc = c + cost[i] + pot[u] - pot[v];
          if (dist[v] > cc) { que.emplace(dist[v] = cc, v); pari[v] = i; }
        }
      }
    }
  }

  // Finds a minimum cost flow from s to t of amount min{(max flow), limFlow}.
  //   Bellman-Ford takes O(n m) time, or O(m) time if there is no negative-cost
  //   edge, or cannot stop if there exists a negative-cost cycle.
  //   min{(max flow), limFlow} shortest paths if Flow is an integral type.
  pair<Flow, Cost> run(int s, int t, Flow limFlow = FLOW_INF) {
    assert(0 <= s); assert(s < n);
    assert(0 <= t); assert(t < n);
    assert(s != t);
    assert(0 <= limFlow);
    pot.assign(n, 0);
    for (; ; ) {
      bool upd = false;
      for (int i = 0; i < m; ++i) if (capa[i] > FLOW_EPS) {
        const int u = zu[i ^ 1], v = zu[i];
        const Cost cc = pot[u] + cost[i];
        if (pot[v] > cc + COST_EPS) { pot[v] = cc; upd = true; }
      }
      if (!upd) break;
    }
    dist.resize(n);
    vis.resize(n);
    pari.resize(n);
    Flow totalFlow = 0;
    Cost totalCost = 0;
    flows.clear(); flows.push_back(0);
    slopes.clear();
    for (; totalFlow < limFlow; ) {
      shortest(s, t);
      if (!vis[t]) break;
      for (int u = 0; u < n; ++u) pot[u] += min(dist[u], dist[t]);
      Flow f = limFlow - totalFlow;
      for (int v = t; v != s; ) {
        const int i = pari[v]; if (f > capa[i]) { f = capa[i]; } v = zu[i ^ 1];
      }
      for (int v = t; v != s; ) {
        const int i = pari[v]; capa[i] -= f; capa[i ^ 1] += f; v = zu[i ^ 1];
      }
      totalFlow += f;
      totalCost += f * (pot[t] - pot[s]);
      flows.push_back(totalFlow);
      slopes.push_back(pot[t] - pot[s]);
    }
    return make_pair(totalFlow, totalCost);
  }
};

////////////////////////////////////////////////////////////////////////////////


int N, K, L;
vector<Int> A, B;


namespace brute {
Int run() {
  MinCostFlow<int, Int> mcf(4 + N + N);
  for (int i = 0; i < N; ++i) {
    const int ua = 4 + i;
    const int ub = 4 + N + i;
    mcf.ae(0, ua, 1, -A[i]);
    mcf.ae(ua, ub, 1, 0);
    mcf.ae(ub, 1, 1, -B[i]);
    mcf.ae(ua, 2, 1, 0);
    mcf.ae(3, ub, 1, 0);
  }
  mcf.ae(2, 3, K - L, 0);
  const auto res = mcf.run(0, 1, K);
  assert(res.first == K);
  return -res.second;
}
}  // brute


namespace fast {
constexpr Int INF = 1001001001001001001LL;
Int ans;
vector<int> usedA, usedB;
int common;
priority_queue<pair<Int, int>> queA, queB, queA1, queB1, queAB;
void useA(int i) {
// cerr<<COLOR("91")<<"[useA] "<<i<<COLOR()<<endl;
  assert(0 <= i); assert(i < N);
  assert(!usedA[i]);
  ans += A[i];
  usedA[i] = 1;
  if (usedB[i]) {
    ++common;
  } else {
    queB1.emplace(B[i], i);
  }
}
void useB(int i) {
// cerr<<COLOR("94")<<"[useB] "<<i<<COLOR()<<endl;
  assert(0 <= i); assert(i < N);
  assert(!usedB[i]);
  ans += B[i];
  usedB[i] = 1;
  if (usedA[i]) {
    ++common;
  } else {
    queA1.emplace(A[i], i);
  }
}
Int run() {
  ans = 0;
  usedA.assign(N + 1, 0);
  usedB.assign(N + 1, 0);
  common = 0;
  queA = {};
  queB = {};
  queA1 = {};
  queB1 = {};
  queAB = {};
  for (int i = 0; i < N; ++i) {
    queA.emplace(A[i], i);
    queB.emplace(B[i], i);
    queAB.emplace(A[i] + B[i], i);
  }
  queA.emplace(-INF, N);
  queB.emplace(-INF, N);
  queA1.emplace(-INF, N);
  queB1.emplace(-INF, N);
  for (int k = 0; k < K; ++k) {
// cerr<<"k = "<<k<<endl;
    for (; usedA[queA.top().second]; queA.pop()) {}
    for (; usedB[queB.top().second]; queB.pop()) {}
    for (; usedA[queA1.top().second]; queA1.pop()) {}
    for (; usedB[queB1.top().second]; queB1.pop()) {}
    for (; usedA[queAB.top().second] || usedB[queAB.top().second]; queAB.pop()) {}
    if (k - common < K - L) {
      useA(queA.top().second);
      useB(queB.top().second);
    } else {
      Int mx = -INF;
      int iA = N, iB = N;
      if (chmax(mx, queA1.top().first + queB.top().first)) {
        iA = queA1.top().second;
        iB = queB.top().second;
      }
      if (chmax(mx, queA.top().first + queB1.top().first)) {
        iA = queA.top().second;
        iB = queB1.top().second;
      }
      if (chmax(mx, queAB.top().first)) {
        iA = iB = queAB.top().second;
      }
      useA(iA);
      useB(iB);
    }
  }
  return ans;
}
}  // fast


int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d%d", &N, &K, &L);
    A.resize(N); for (int i = 0; i < N; ++i) scanf("%lld", &A[i]);
    B.resize(N); for (int i = 0; i < N; ++i) scanf("%lld", &B[i]);
cerr<<"N = "<<N<<", K = "<<K<<", L = "<<L<<endl;
    
    const Int ans = fast::run();
    printf("%lld\n", ans);
#ifdef LOCAL
if(N<=2000){
 const Int brt=brute::run();
 if(brt!=ans){
  cerr<<"N = "<<N<<", K = "<<K<<", L = "<<L<<endl;
  cerr<<"A = "<<A<<endl;
  cerr<<"B = "<<B<<endl;
  cerr<<"brt = "<<brt<<endl;
  cerr<<"ans = "<<ans<<endl;
 }
 assert(brt==ans);
}
#endif
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

詳細信息

Test #1:

score: 4
Accepted
time: 0ms
memory: 3704kb

input:

10
5 2 1
965603156 594151484 137421888 511721918 163053182
239833925 530765178 939584446 407283748 456390712
6 3 1
563597651 744310197 650756091 459159791 905965537 501095539
436402349 255689803 349243909 650771685 210810349 498904461
5 2 1
22583989 839924760 708231676 112954530 76654839
903218601 4...

output:

3030104264
3799951880
2863125946
1325410849
4211946604
1159081424
5130538185
1723509214
1064449794
2987648361

result:

ok 10 lines

Test #2:

score: 4
Accepted
time: 1ms
memory: 3660kb

input:

10
10 5 3
616184425 976452539 761981097 695457891 763840505 968348264 566556887 265617181 58911367 482603223
45532958 653449971 782683026 193186869 888757559 333111221 3349873 784911610 686154761 121266222
9 5 3
330072780 326255202 80272705 125430104 102075855 828287907 235531636 70735517 750894981
...

output:

7962037223
6552073731
6453906018
5929326323
6940770119
6659162581
6297542711
6646897675
6376238030
7131857717

result:

ok 10 lines

Test #3:

score: 4
Accepted
time: 1ms
memory: 3704kb

input:

10
10 5 3
649845555 72720877 993419727 263881028 305586400 288643288 156388276 319379522 438816973 290855311
323296929 488918848 327687849 567259099 592784910 455296335 92089934 998566774 10383678 686621630
10 5 2
923267213 304913474 971262391 726541470 800369439 689021980 170326210 806899275 785571...

output:

5893237776
7076600204
6717261021
7508233375
6923400251
7403936865
6923547974
7398327563
7081909406
6308829190

result:

ok 10 lines

Test #4:

score: 4
Accepted
time: 1ms
memory: 3692kb

input:

10
13 6 4
744504845 465640191 742840710 749591534 637106834 466615185 647043521 944195299 920660760 960803731 426930320 50760325 12131990
225882700 951214848 386981596 702206249 810845170 935921878 400748831 607597330 988515464 24365757 138049895 515479818 75862154
14 8 6
364916038 799465121 8508562...

output:

9953163942
9815605264
10293263995
9089575827
11276548270
11603081934
20900000001
10210433748
9158479164
10407512731

result:

ok 10 lines

Test #5:

score: 4
Accepted
time: 1ms
memory: 3700kb

input:

10
17 9 4
962764835 362315292 13630273 999056368 593113392 316684021 270366369 524750 436266826 546825314 542769251 968051293 902487850 313550766 352444767 496012551 500025800
60260534 781741754 950862833 380833506 868207510 897502587 711134091 415405 597366363 63217028 308470194 650657391 994150629...

output:

13343563318
17256870659
13583263399
28900000001
10475330081
11013646810
13884244114
14166608938
11341667465
14134861328

result:

ok 10 lines

Test #6:

score: 4
Accepted
time: 0ms
memory: 3704kb

input:

10
23 13 11
217763594 448293943 60749904 638025617 986118931 904063126 914129023 730064931 652601925 160932317 158612763 421349034 509829433 856377654 376806108 245065327 84696262 821570570 373731004 277363452 457843207 727961601 799920628
47231952 46728198 195523551 999942121 69962028 387752080 609...

output:

16473214307
15081268888
16065177766
15554712540
16783392810
26900000006
19673628566
13737251726
16873407662
16554908888

result:

ok 10 lines

Test #7:

score: 4
Accepted
time: 1ms
memory: 3692kb

input:

10
30 22 15
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 999999999 999999999 999999999 500000000 500000000 500000000 900000000 500000000 500000001 500000001 500000001 1 1 1 1
10000...

output:

38900000006
21390894969
22514207512
21974532768
22485860422
20207075223
24915834513
23445066279
22376603784
23462471141

result:

ok 10 lines

Test #8:

score: 4
Accepted
time: 0ms
memory: 3712kb

input:

10
90 52 47
919368836 898778007 155887555 418878350 296550352 412039356 10081056 643649003 923665904 379222505 392431293 917794821 416595148 505987222 812625571 50883444 100534926 328861309 254382363 530073617 388652958 832571799 835963054 801123318 526081190 810560540 903286821 299049339 550657678 ...

output:

68468885389
61534810719
62435494684
62867966042
57557979045
49256223011
74395012570
70234377679
65917846116
120900000016

result:

ok 10 lines

Test #9:

score: 4
Accepted
time: 1ms
memory: 3724kb

input:

10
150 76 15
430001693 909102825 25930110 730304321 231817785 675369349 562583012 897811860 207898441 843807802 962609870 284926499 599226773 914830209 279610145 879706032 105520474 292243845 254424352 638565660 925816753 309283301 337162309 292480574 987028494 581015653 455317385 767145294 27608924...

output:

113037522748
114105290197
113852119186
118643149339
152900000051
113040175034
126931644232
122116468862
116482229575
119330323686

result:

ok 10 lines

Test #10:

score: 4
Accepted
time: 1ms
memory: 3740kb

input:

10
150 87 57
988378168 76630186 134239432 445733378 391458284 627828766 546901084 165369589 481361775 6251876 986127782 654205865 176693026 418690539 387857449 367314096 449963429 130488676 914618788 394172633 13636057 534370754 587481113 596003126 971380448 338996019 947778506 969298713 103340570 1...

output:

121540737758
120939180499
100092942266
120622440918
125117838215
124394630987
117577683526
124727994475
138900000056
124284469630

result:

ok 10 lines

Test #11:

score: 4
Accepted
time: 0ms
memory: 3812kb

input:

10
600 312 114
579483035 989149124 512631787 219742074 208722697 309189432 194502593 256303936 212082432 673890067 213083236 607797967 912453955 483719456 984766662 649314678 928077207 761899468 382974247 949207927 423527297 559663178 773405417 176739655 82027052 157380043 185700403 184679544 462411...

output:

457495345535
471494197381
498514924828
452313606251
469885179010
415213299847
455820449704
744900000161
435222658118
484246563958

result:

ok 10 lines

Test #12:

score: 4
Accepted
time: 2ms
memory: 3964kb

input:

10
1500 787 531
11566933 803713562 768699001 834998150 449099974 423238333 843886747 603244709 647696567 688772974 862546669 763633618 269636808 569545221 200213253 22224806 602725364 179497202 139813991 944257259 985125101 912487992 340919109 982707730 28240001 135241300 995845260 194095903 6416302...

output:

1050028961662
1237126997366
1149947992197
1632900000486
1187758519576
1142688560191
1182736811080
1269921652926
1182780551662
1160103411491

result:

ok 10 lines

Test #13:

score: 4
Accepted
time: 8ms
memory: 3948kb

input:

10
2000 1157 368
296531338 709434921 911761453 474324740 102930264 305301471 525862850 128492824 773085090 992587216 716931224 893253957 126480487 89754272 391511679 336369662 183798748 693797835 281173678 418991426 551814429 505061648 467519975 995172261 941365074 537978940 504269024 307169323 7401...

output:

1673192654791
1591882551707
1466800089650
1602011025957
1679734511667
2536900000521
1518017365981
1547604621333
1514199745790
1499876993202

result:

ok 10 lines

Test #14:

score: 4
Accepted
time: 7ms
memory: 3884kb

input:

10
2000 1180 855
862862449 460005242 23632600 510996210 209285804 573896772 133861214 395787356 936104691 902469115 244732037 107849778 256192194 262398187 413442667 377450848 755503319 55399586 760234605 905957395 920924973 357872620 590163240 555028408 22558979 122176215 49321081 664637180 4222225...

output:

1659742997845
1613318845845
1511646819254
1556753158189
1607869441380
1976900000721
1613430687311
1645227651392
1628511772111
1543465469535

result:

ok 10 lines

Test #15:

score: 4
Accepted
time: 7ms
memory: 3812kb

input:

10
2000 1180 855
862862449 460005242 23632600 510996210 209285804 573896772 133861214 395787356 936104691 902469115 244732037 107849778 256192194 262398187 413442667 377450848 755503319 55399586 760234605 905957395 920924973 357872620 590163240 555028408 22558979 122176215 49321081 664637180 4222225...

output:

1659742997845
1613318845845
1511646819254
1556753158189
1607869441380
1976900000721
1613430687311
1645227651392
1628511772111
1543465469535

result:

ok 10 lines

Test #16:

score: 4
Accepted
time: 7ms
memory: 3812kb

input:

10
2000 1171 871
120073009 778537945 587664391 649676281 410037533 623708099 161304083 866841664 624743933 47402288 800110565 365139332 190733638 584979941 701919379 655108396 751103918 15216360 77581937 222879707 929171241 771878525 294893845 962127736 791611627 369749546 718832980 524658470 673692...

output:

1619326682849
1638678775569
1516875240347
1570887984315
1569397636561
1543322242050
1504976236266
1619444013549
1626037963374
1932900000736

result:

ok 10 lines

Test #17:

score: 4
Accepted
time: 36ms
memory: 4548kb

input:

10
10000 5591 4785
631794873 36811505 570329778 409542253 296452559 537054330 808194551 868054763 206138249 456846664 881959381 676849993 246372766 420080479 873371039 976331563 151552770 720314373 636522986 809011062 894388203 987446718 73409676 95493711 24934348 667048527 833891482 451312922 71336...

output:

7699112650565
7712429983905
7979353519236
7730182130651
7423290163090
7901088837222
7965311772778
8386900004146
8282721938767
7904964757250

result:

ok 10 lines

Test #18:

score: 4
Accepted
time: 55ms
memory: 8520kb

input:

10
20000 11109 2227
343343837 892638556 247682475 476492414 324732966 726184769 828172147 712193248 165590797 615976657 954555515 838985579 841602960 981985967 517003091 274061833 178269518 989341468 197254037 700770745 558684218 410995432 448965583 304524068 795893638 365991769 827684611 401995348 ...

output:

16319932459199
8179045767493
7672081505754
17022051505372
7870417654273
7545641603113
40216150497503
13146900002446
7670192224639
6965559145029

result:

ok 10 lines

Test #19:

score: 4
Accepted
time: 116ms
memory: 20040kb

input:

10
10000 5552 3641
958190609 297888815 681846063 827829258 972141798 92450439 625625860 676130749 505822860 891850810 482201140 10221949 999332582 888512125 381527106 205316640 14283035 312085957 34447350 192351163 947059598 515357639 666788690 808546722 933619173 291237753 847403934 470035563 42726...

output:

7975683141306
7166591501570
8099788005436
8750900004016
8431226003621
156217255503911
7398761157628
7649240014345
7696109621131
7779812943379

result:

ok 10 lines

Test #20:

score: 4
Accepted
time: 108ms
memory: 20108kb

input:

10
1000 586 421
809462471 649085888 680301237 799124096 564972585 484214631 575760742 177122762 589185011 802971266 235012892 200265837 208383600 428760812 126983745 724286052 164889127 522357949 784432509 883653094 989081058 593836623 228055482 303203693 995938475 637777977 459851296 678684081 4204...

output:

801834838857
796494573308
818931781550
49200900018141
810895491911
805405670977
148186619576480
30732210946430
740658144071
3020688543369

result:

ok 10 lines

Test #21:

score: 4
Accepted
time: 146ms
memory: 21404kb

input:

10
1000 523 318
767380751 841060657 606544357 30866903 762244472 103448834 160215738 529713012 771063132 247518450 898729046 642653381 61774435 819254330 168266882 77640994 158906486 880754259 666010951 976432677 561649599 348698869 620804334 13659557 228716711 132093466 915566593 243024829 37615816...

output:

754607364301
742209480052
758348700088
10094900003536
823584900123
163747894656350
801223368621
62687939042550
822067343219
3222488673290

result:

ok 10 lines

Test #22:

score: 4
Accepted
time: 291ms
memory: 21616kb

input:

10
50000 27143 10544
534146034 962255176 106431813 478751291 729001096 401047848 549698618 927169831 532541988 50007740 914686927 165699410 462469729 527454778 726929 857589681 470965749 458179398 991162524 130725179 561249144 377232867 161134992 832697335 970250995 382731142 902143349 900327790 180...

output:

39214961764496
40320930618152
39478116544076
162600433707100
38511662404315
41758618250788
40249518813336
65720900012241
41183041354913
40931003878772

result:

ok 10 lines

Test #23:

score: 4
Accepted
time: 327ms
memory: 25644kb

input:

10
200000 140487 80975
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10...

output:

233364900059511
158370092256571
41056117237583
39110325112397
7481336529399
7574661269081
162189313326199
7539167723630
8198330781151
3990518442

result:

ok 10 lines

Test #24:

score: 4
Accepted
time: 445ms
memory: 23012kb

input:

10
100000 54662 30043
385571789 357043330 345092198 445042298 267544251 643919947 724763377 513274307 329395489 372439525 656954840 557207399 154589846 610232115 229679695 543270634 319600621 257403228 134011595 583885585 360780603 826309827 304011010 731094498 756386775 776863503 721461223 74609577...

output:

79429549473790
15885147061011
151691700110685
19846900007196
155016074957365
16462081180823
150677910863034
15820011579899
15675568859981
147729086475133

result:

ok 10 lines

Test #25:

score: 4
Accepted
time: 448ms
memory: 25040kb

input:

10
100000 51610 9243
334561204 539786866 556522749 640980766 501115470 911646373 617279715 665143741 340182338 348741431 27578859 564229352 94174942 395730829 235026756 888277878 286985326 295994628 256005531 784641265 880744694 635817779 389589926 928391256 980879641 896015409 730215453 735549866 9...

output:

77532349332131
15983329396224
154442227853459
165777353038347
15746778342932
15788719225548
14498855841499
16144342625775
184630900076916
162916848700973

result:

ok 10 lines

Extra Test:

score: 0
Extra Test Passed