QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#396954#7762. 数据库alpha1022100 ✓82ms4928kbC++143.1kb2024-04-23 14:48:082024-04-23 14:48:09

Judging History

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

  • [2024-04-23 14:48:09]
  • 评测
  • 测评结果:100
  • 用时:82ms
  • 内存:4928kb
  • [2024-04-23 14:48:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

template<class Z, class ZC>
struct CostFlow {
  int n;
  vector<vector<tuple<int, int, Z, ZC>>> g;

  CostFlow(int n) : n(n), g(n) {}

  void addEdge(int u, int v, Z c, ZC w) {
    int ru = g[u].size(), rv = g[v].size();
    g[u].emplace_back(v, rv, c, w), g[v].emplace_back(u, ru, 0, -w);
  }

  pair<Z, ZC> dinic(int s, int t) {
    vector<ZC> h(n), dis(n);
    vector<int> level(n), inQueue(n), cur(n);
    auto getH = [&]() {
      fill_n(h.begin(), n, numeric_limits<ZC>::max());
      queue<int> q; q.push(s), h[s] = 0, inQueue[s] = 1;
      while (!q.empty()) {
        int u = q.front(); q.pop(), inQueue[u] = 0;
        for (auto [v, _, c, w]: g[u]) {
          if (c && h[v] > h[u] + w) {
            h[v] = h[u] + w;
            if (!inQueue[v]) q.push(v), inQueue[v] = 1;
          }
        }
      }
    };
    getH();
    if (h[t] == numeric_limits<ZC>::max()) return {0, 0};
    auto getLevel = [&]() {
      fill_n(dis.begin(), n, numeric_limits<ZC>::max());
      priority_queue<pair<ZC, int>, vector<pair<ZC, int>>, greater<pair<ZC, int>>> pQ;
      pQ.emplace(dis[s] = 0, s);
      while (!pQ.empty()) {
        auto [d, u] = pQ.top(); pQ.pop();
        if (d > dis[u]) continue;
        for (auto [v, _, c, w]: g[u]) {
          w += h[u] - h[v];
          if (c && dis[v] > dis[u] + w) pQ.emplace(dis[v] = dis[u] + w, v);
        }
      }
      queue<int> q; fill_n(level.begin(), n, -1), q.push(s), level[s] = 0;
      while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [v, _, c, w]: g[u])
          if (c && dis[v] == dis[u] + w + h[u] - h[v] && level[v] == -1) level[v] = level[u] + 1, q.push(v);
      }
    };
    Z ret = 0; ZC cost = 0;
    function<Z(int, Z)> cap = [&](int u, Z lim) {
      if (u == t) return lim;
      Z ret = 0;
      for (; cur[u] && ret < lim; --cur[u]) {
        auto &[v, rev, c, w] = g[u][cur[u] - 1];
        if (c && dis[v] == dis[u] + w + h[u] - h[v] && level[v] == level[u] + 1) {
          Z flow = cap(v, min(lim - ret, c));
          ret += flow, cost += flow * w, c -= flow, get<2>(g[v][rev]) += flow;
          if (ret == lim) return ret;
        }
      }
      return ret;
    };
    while (getLevel(), level[t] != -1) {
      for (int i = 0; i < n; ++i) cur[i] = g[i].size();
      ret += cap(s, numeric_limits<Z>::max());
      for (int i = 0; i < n; ++i) h[i] += dis[i];
    }
    return {ret, cost};
  }
};

int main() {
  int m, n, k, s, t; scanf("%d%d%d", &n, &m, &k);
  vector<int> w(n), a(k);
  for (int &i : w) scanf("%d", &i);
  for (int &i : a) scanf("%d", &i), --i;
  a.erase(unique(a.begin(), a.end()), a.end()), s = k = a.size(), t = k - 1;
  CostFlow<int, int> costFlow(k + 1);
  int ans = 0;
  vector<int> las(n, -1);
  costFlow.addEdge(s, 0, m - 1, 0);
  for (int i = 0; i + 1 < k; ++i) costFlow.addEdge(i, i + 1, numeric_limits<int>::max(), 0);
  for (int i = 0; i < k; ++i) {
    if (las[a[i]] != -1) costFlow.addEdge(las[a[i]] + 1, i, 1, -w[a[i]]);
    las[a[i]] = i, ans += w[a[i]];
  }
  printf("%d\n", ans += costFlow.dinic(s, t).second);
}

詳細信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 78ms
memory: 4904kb

input:

10 3 5000
23077 34848 88221 8067 83132 62621 41320 69146 32971 27594
2 7 5 3 9 6 1 9 4 8 1 8 8 3 6 9 1 7 5 5 6 8 1 3 10 6 8 7 10 2 1 2 6 7 5 5 9 5 7 10 10 6 6 7 2 4 3 1 10 10 5 1 1 6 1 2 8 9 2 5 10 1 10 7 5 5 10 5 2 5 6 10 9 5 6 3 5 3 6 5 7 4 1 5 8 1 1 9 7 1 1 2 1 8 6 2 9 8 4 2 5 4 5 2 10 4 3 6 9 7 ...

output:

100598924

result:

ok single line: '100598924'

Test #2:

score: 0
Accepted
time: 77ms
memory: 4624kb

input:

10 4 5000
54224 55364 32836 46635 99179 26033 49587 15072 63093 94302
4 7 8 4 1 2 6 3 1 1 6 10 5 7 2 9 3 9 1 5 7 3 8 4 7 2 5 3 5 4 1 6 4 10 4 10 8 1 5 7 9 7 9 1 6 1 10 10 10 5 1 1 3 5 10 1 8 8 6 8 8 10 6 9 7 6 1 1 5 3 10 8 6 5 8 7 5 8 4 8 8 1 8 6 4 5 8 10 7 6 7 2 10 7 10 10 3 1 3 5 5 7 3 2 5 3 1 7 6...

output:

85562058

result:

ok single line: '85562058'

Test #3:

score: 0
Accepted
time: 79ms
memory: 4928kb

input:

10 5 5000
8091 5917 35634 83114 46741 61842 48134 41606 63881 20560
8 7 9 5 1 4 10 9 10 9 8 5 5 7 5 1 5 9 4 1 4 7 9 4 10 4 4 2 9 1 5 1 2 6 10 1 5 4 5 3 3 1 6 7 5 7 10 2 5 8 2 9 3 5 3 1 2 4 5 10 4 4 10 4 8 2 8 6 4 1 3 6 8 2 6 2 2 5 9 4 2 8 3 10 8 7 2 1 10 6 5 8 2 8 9 3 9 5 6 6 7 2 7 3 10 9 10 2 4 7 2...

output:

43892491

result:

ok single line: '43892491'

Subtask #2:

score: 20
Accepted

Test #4:

score: 20
Accepted
time: 73ms
memory: 4640kb

input:

10 2 5000
65644 5214 85000 40719 98071 56616 35404 16019 96748 89032
5 9 6 1 3 6 8 10 2 9 1 10 5 9 9 9 2 7 7 7 7 10 5 1 3 10 4 2 5 5 2 8 3 2 1 3 3 6 2 4 5 5 2 5 2 3 4 2 10 1 4 6 10 9 6 4 9 10 5 3 9 7 7 2 1 9 5 8 8 4 8 8 4 5 6 1 3 4 8 10 4 3 6 6 9 2 5 2 8 5 10 4 7 10 3 9 3 2 9 3 10 7 1 3 9 9 3 5 1 3 ...

output:

173524192

result:

ok single line: '173524192'

Test #5:

score: 0
Accepted
time: 53ms
memory: 4720kb

input:

100 2 5000
49570 6371 37107 2261 33457 98048 84700 76277 32602 53831 20995 86351 57905 93492 65198 80688 44394 48442 57924 88655 16250 11904 21033 99426 59241 71456 7697 85276 81310 49884 64543 72091 63969 23936 88032 62420 42269 76663 37639 16930 61480 97674 38809 77434 25043 46618 93378 74399 1031...

output:

231972847

result:

ok single line: '231972847'

Test #6:

score: 0
Accepted
time: 18ms
memory: 4680kb

input:

1000 2 5000
40824 4748 88829 17859 98470 82824 82849 16663 96731 71333 73050 75770 22643 62690 87789 72306 46178 68415 85222 18729 54074 53251 45445 35978 1417 85067 89297 42145 43426 1108 28947 87941 49299 51501 80512 41395 71615 26966 60841 87838 41260 59483 31968 54392 50188 65874 275 38593 32941...

output:

241831233

result:

ok single line: '241831233'

Subtask #3:

score: 20
Accepted

Test #7:

score: 20
Accepted
time: 1ms
memory: 4228kb

input:

5000 15 400
34145 93322 29976 7963 53362 50640 10859 94528 13329 49980 18826 50286 60155 79748 73253 18329 5216 83079 48220 98825 46592 76855 14037 19859 80960 4461 377 70496 28092 99806 5355 27013 92051 95231 65553 32365 3862 89764 86063 93033 12754 68996 38965 52942 69948 34370 3023 52079 16066 57...

output:

19341503

result:

ok single line: '19341503'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

5000 15 400
68511 70579 96844 20943 72871 28340 68790 60294 76760 12623 80406 65418 37942 2849 76307 28818 18555 42151 94506 78241 15350 11345 76323 21860 22703 31009 24763 71007 60858 53746 28720 5027 72512 39122 55299 41675 88475 94331 78711 3464 80345 69031 98746 14792 97862 97255 5853 92742 9096...

output:

19515326

result:

ok single line: '19515326'

Test #9:

score: 0
Accepted
time: 1ms
memory: 4192kb

input:

5000 15 400
18305 15347 86331 37503 78391 3378 82447 51150 49032 2422 47659 20516 18666 16520 27948 17865 45842 66799 35584 75288 46358 21654 30233 25291 44810 27579 93986 15174 56012 48286 66826 93615 77979 40669 17262 77857 82134 50752 19642 77961 55856 68600 60598 33035 94214 17392 16736 21460 58...

output:

18253485

result:

ok single line: '18253485'

Subtask #4:

score: 20
Accepted

Test #10:

score: 20
Accepted
time: 4ms
memory: 4288kb

input:

10 5 1000
86764 81108 88408 93029 87155 18790 28170 29349 81866 77109
8 7 10 7 2 7 1 8 4 10 9 10 4 1 7 1 9 9 1 6 6 1 9 6 7 1 8 10 1 7 9 1 1 9 7 10 8 5 5 1 2 3 10 6 2 6 2 6 1 2 7 8 5 6 10 2 9 8 2 6 8 5 10 8 1 10 4 6 5 6 3 8 1 3 5 2 2 7 2 4 5 5 8 2 4 1 3 6 8 2 2 3 1 8 1 5 8 6 9 7 7 3 7 9 8 9 9 7 5 3 6...

output:

15248002

result:

ok single line: '15248002'

Test #11:

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

input:

10 10 1000
57793 91210 18011 676 38391 78527 56352 69343 95947 5616
5 8 4 5 10 6 1 7 3 10 2 7 1 9 5 3 5 8 3 8 7 10 2 10 6 1 4 3 6 10 6 3 8 4 3 9 1 6 10 3 10 1 6 2 9 9 3 5 8 8 3 9 1 5 9 9 3 3 7 9 2 4 1 9 8 3 1 2 8 9 10 9 4 3 10 5 4 4 8 6 6 9 3 3 2 3 7 2 3 3 10 4 5 5 6 4 2 5 10 1 2 6 9 8 7 9 4 8 2 1 2...

output:

511866

result:

ok single line: '511866'

Test #12:

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

input:

10 15 1000
19536 14188 62086 25660 67447 48774 97871 17167 8671 85361
3 5 2 6 4 6 10 5 7 6 10 8 1 9 5 7 5 5 2 10 7 10 8 6 3 4 2 2 8 9 6 10 9 10 10 9 6 1 7 2 1 10 8 10 3 9 1 8 10 4 6 9 9 8 1 5 2 10 9 1 3 6 5 6 2 5 3 9 6 5 6 10 5 6 10 4 6 6 8 8 9 5 2 10 1 10 7 4 2 6 10 5 6 2 3 1 3 9 8 3 9 7 7 7 2 6 7 ...

output:

446761

result:

ok single line: '446761'

Test #13:

score: 0
Accepted
time: 2ms
memory: 4260kb

input:

100 5 1000
95646 33117 46458 52069 38647 38645 60235 93897 41039 35835 49580 92470 5371 6812 38049 9178 50163 92322 9735 27037 58888 49095 68473 5472 1644 94513 50597 10246 96329 51334 1986 79907 89526 10771 29923 55249 59048 91934 46853 79352 85644 57708 57300 20536 70782 61882 58712 97314 45686 55...

output:

36018137

result:

ok single line: '36018137'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3996kb

input:

100 10 1000
36326 35981 96633 82565 65884 23199 50344 49682 96971 42033 2351 31928 50056 73426 36217 89994 30603 27971 17757 19901 99501 35915 27895 26451 91714 36134 94294 19114 22490 97680 48272 80639 24603 93000 28420 7595 7314 52546 12258 58666 88422 29237 69223 41046 13515 72493 26486 34554 239...

output:

30951978

result:

ok single line: '30951978'

Test #15:

score: 0
Accepted
time: 2ms
memory: 4084kb

input:

100 15 1000
60259 28844 6884 35222 45974 11055 13021 13966 14853 85552 12283 29760 50104 63448 84364 1684 99886 31837 61724 84415 28292 81814 31562 60077 93784 1729 1602 56374 19276 89781 13359 78765 97380 34118 39756 12254 61197 53500 95962 61254 16553 24467 58101 53482 65199 75076 67326 92045 306 ...

output:

26014456

result:

ok single line: '26014456'

Test #16:

score: 0
Accepted
time: 0ms
memory: 4080kb

input:

1000 5 1000
84587 68464 19119 74315 48972 23581 58263 43666 21662 5458 47594 18617 52236 24283 45998 66734 8501 94413 31981 77247 50069 95649 21536 8055 62698 98164 14074 22987 14525 12396 7681 17830 97091 88885 86419 1067 92977 54999 33673 9550 67710 98546 82017 17583 667 36168 61540 74015 42193 48...

output:

45688268

result:

ok single line: '45688268'

Test #17:

score: 0
Accepted
time: 2ms
memory: 4036kb

input:

1000 10 1000
24129 67704 68122 93372 94874 19813 14041 20830 97805 57074 99877 64455 80825 93755 98668 89675 35445 42895 74964 71326 43884 8123 1767 83698 2892 77832 21668 85066 17440 49874 77903 22427 45669 41174 40029 27379 61235 13563 4313 90065 99573 45555 19683 39486 76606 30438 34528 180 83016...

output:

44994110

result:

ok single line: '44994110'

Test #18:

score: 0
Accepted
time: 3ms
memory: 4068kb

input:

1000 15 1000
59991 63683 65484 87716 79869 15955 13746 80474 77381 51499 17028 13036 18275 82716 12845 66038 16310 66787 28778 73107 90796 63216 85094 24799 99979 96956 35994 21067 81494 75695 91088 34745 82075 27522 293 67267 51879 50823 80429 54323 21127 60258 40463 26950 69326 7049 39530 62048 23...

output:

39885004

result:

ok single line: '39885004'

Subtask #5:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #19:

score: 20
Accepted
time: 76ms
memory: 4628kb

input:

10 5 5000
95311 97197 20634 42609 6109 19539 52553 34009 78555 1142
1 2 4 4 5 8 9 1 1 6 8 3 5 7 1 10 5 1 3 3 10 6 3 6 2 7 9 8 8 3 4 3 7 4 5 5 4 10 5 10 10 9 3 8 6 1 10 5 2 3 7 8 7 8 1 1 5 9 7 4 1 4 7 6 5 8 1 5 6 10 10 3 4 3 9 7 7 9 7 7 9 10 9 5 6 8 4 8 5 2 1 2 1 1 3 10 6 8 5 8 2 1 7 9 2 3 10 3 5 7 6...

output:

39375079

result:

ok single line: '39375079'

Test #20:

score: 0
Accepted
time: 82ms
memory: 4724kb

input:

10 10 5000
98273 81150 13203 63792 62989 68848 18153 51586 86054 21067
6 5 4 2 7 4 7 3 6 8 10 10 3 6 8 2 6 3 4 3 10 10 4 6 2 1 3 9 3 3 2 9 5 10 7 7 4 6 10 4 4 4 10 2 6 4 1 4 2 10 10 9 9 9 7 7 6 10 3 5 7 5 2 1 2 3 10 8 5 8 3 3 3 5 7 10 2 9 9 2 5 4 3 10 3 3 1 6 3 4 6 3 7 3 1 2 9 1 1 5 6 6 2 2 8 3 6 2 ...

output:

565115

result:

ok single line: '565115'

Test #21:

score: 0
Accepted
time: 79ms
memory: 4840kb

input:

10 15 5000
20970 25816 24101 23700 61706 61875 77329 13964 74318 97247
7 6 10 3 2 6 3 5 9 1 9 3 5 1 4 2 9 3 1 10 3 7 4 6 6 7 6 5 10 2 2 4 7 3 5 4 5 5 6 1 7 3 4 9 2 5 2 8 10 8 9 2 1 9 6 8 8 1 3 9 5 4 4 9 8 6 8 5 6 1 7 8 5 10 1 6 4 7 6 8 6 3 3 4 1 3 3 3 2 10 4 1 7 1 8 6 1 4 5 4 10 7 10 10 8 5 8 4 1 8 ...

output:

481026

result:

ok single line: '481026'

Test #22:

score: 0
Accepted
time: 56ms
memory: 4676kb

input:

100 5 5000
82265 27396 37949 28176 45237 34409 24299 19260 97138 7806 11205 22276 24145 24012 2950 88173 46881 52393 66140 14699 19428 58547 62523 34156 45844 30098 80722 57225 24816 14406 56436 68952 36291 70528 5366 4555 72840 58234 34352 80140 58896 45050 38565 3238 13155 73657 46485 97057 73756 ...

output:

180542020

result:

ok single line: '180542020'

Test #23:

score: 0
Accepted
time: 56ms
memory: 4712kb

input:

100 10 5000
22169 12813 88304 40455 10281 18907 64693 47565 13409 62511 3853 63418 24595 66654 85487 93750 69039 7744 35597 40330 34209 23965 21348 64835 37341 42273 15017 31758 80295 45378 36239 19323 90871 29532 38399 56205 53307 36733 15370 12770 35492 45749 24809 32213 61667 63643 86450 85193 87...

output:

141036182

result:

ok single line: '141036182'

Test #24:

score: 0
Accepted
time: 63ms
memory: 4712kb

input:

100 15 5000
64246 83055 55833 75339 52574 80114 72346 81503 87242 41861 99212 65268 71249 2271 71164 8676 88853 75166 83495 69747 62514 37429 36206 86722 59503 60607 9258 65996 47445 91791 4437 37356 94846 93360 6907 38115 38894 17102 89623 93353 49440 53929 21125 55225 22551 6037 46393 34624 22644 ...

output:

132198375

result:

ok single line: '132198375'

Test #25:

score: 0
Accepted
time: 24ms
memory: 4488kb

input:

1000 5 5000
41240 14623 28193 36469 20095 8769 77577 23805 90005 23158 23246 86494 47204 92461 52274 43422 37817 53650 88920 79626 72624 88762 93787 75359 55621 23837 47645 35756 53478 35915 19083 92980 55350 92698 68852 36347 37169 75824 3392 74231 80854 6930 69203 27736 68343 84636 44820 58736 863...

output:

226732461

result:

ok single line: '226732461'

Test #26:

score: 0
Accepted
time: 20ms
memory: 4588kb

input:

1000 10 5000
81171 39433 932 57246 34719 18096 54304 74007 53578 13900 80179 19308 97376 55015 55153 29120 9904 95342 53091 61149 36545 60673 83917 77254 88290 40622 74743 10916 78728 47444 13822 3028 30546 90665 98103 96666 13916 81204 17778 96530 57703 27255 56193 62387 96913 86085 76184 43446 778...

output:

214668648

result:

ok single line: '214668648'

Test #27:

score: 0
Accepted
time: 33ms
memory: 4624kb

input:

1000 15 5000
62006 33664 59024 89253 60707 61536 40390 20091 42668 52207 31837 48452 8485 86813 95462 44053 66961 54191 94315 2008 80036 17610 74422 30391 62046 8348 83036 24282 20216 34594 24830 50138 14964 11931 97033 17142 38633 63400 63880 59935 83338 33934 15594 58821 23850 2021 95506 73831 644...

output:

207259065

result:

ok single line: '207259065'