QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624460#7064. Spybright_ml#TL 452ms12520kbC++203.3kb2024-10-09 15:53:322024-10-09 15:53:32

Judging History

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

  • [2024-10-09 15:53:32]
  • 评测
  • 测评结果:TL
  • 用时:452ms
  • 内存:12520kb
  • [2024-10-09 15:53:32]
  • 提交

answer

//
// Created by 35395 on 2024/10/9.
//
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define PII pair<ll, ll>
#define fi first
#define se second

const int N = 410;

int n;
ll b[N], c[N], sum[N];
PII a[N];

struct MCFGraph {
    struct Edge {
        int v, c, f;
        Edge(int v, int c, int f) : v(v), c(c), f(f) {}
    };
    const int n;
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> h, dis;
    std::vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n, std::numeric_limits<int>::max());
        pre.assign(n, -1);
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> que;
        dis[s] = 0;
        que.emplace(0, s);
        while (!que.empty()) {
            int d = que.top().first;
            int u = que.top().second;
            que.pop();
            if (dis[u] < d) continue;
            for (int i : g[u]) {
                int v = e[i].v;
                int c = e[i].c;
                int f = e[i].f;
                if (c > 0 && dis[v] > d + h[u] - h[v] + f) {
                    dis[v] = d + h[u] - h[v] + f;
                    pre[v] = i;
                    que.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != std::numeric_limits<int>::max();
    }
    MCFGraph(int n) : n(n), g(n) {}
    void addEdge(int u, int v, int c, int f) { // 最大流
        g[u].push_back(e.size());
        e.emplace_back(v, c, f);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -f);
    }

    std::pair<int, int> flow(int s, int t) {
        int flow = 0;
        int cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0; i < n; ++i) h[i] += dis[i];
            int aug = std::numeric_limits<int>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) aug = std::min(aug, e[pre[i]].c);
            for (int i = t; i != s; i = e[pre[i] ^ 1].v) {
                e[pre[i]].c -= aug;
                e[pre[i] ^ 1].c += aug;
            }
            flow += aug;
            cost += int(aug) * h[t];
        }
        return std::make_pair(flow, cost);
    }
};

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].fi;
    }
    for(int i = 1; i <= n; i++) {
        cin >> a[i].se;
    }
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
    }

    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i].se;
    }

    int s = n + n + 1, t = s + 1;
    MCFGraph g(2 * n + 3);
    for(int i = 1; i <= n; i++) {
        g.addEdge(s, i, 1, 0);
        g.addEdge(i + n, t, 1, 0);
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            int l = 0, r = n;
            while(l < r) {
                int mid = (l + r + 1) >> 1;
                if(a[mid].fi >= b[i] + c[j]) {
                    r = mid - 1;
                } else {
                    l = mid;
                }
            }
            g.addEdge(i, n + j, 1, -sum[l]);
        }
    }

    cout << -g.flow(s, t).second << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

input:

4
1 2 3 4
1 1 1 1
0 0 1 1
0 1 1 2

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 252ms
memory: 12520kb

input:

400
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...

output:

160000

result:

ok single line: '160000'

Test #3:

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

input:

40
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 10000000000000000...

output:

1600

result:

ok single line: '1600'

Test #4:

score: 0
Accepted
time: 249ms
memory: 11832kb

input:

400
4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000...

output:

160000

result:

ok single line: '160000'

Test #5:

score: 0
Accepted
time: 265ms
memory: 11620kb

input:

400
-400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -...

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 253ms
memory: 12188kb

input:

400
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 27644 32662 ...

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 262ms
memory: 11280kb

input:

400
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

400

result:

ok single line: '400'

Test #8:

score: 0
Accepted
time: 263ms
memory: 11348kb

input:

400
-1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1...

output:

0

result:

ok single line: '0'

Test #9:

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

input:

10
7 7 7 7 7 7 7 7 7 7
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 3
4 4 4 4 4 4 4 4 4 3

output:

0

result:

ok single line: '0'

Test #10:

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

input:

2
0 1
1 1
0 1
0 2

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Accepted
time: 421ms
memory: 12292kb

input:

400
13847081798897 874663680339 -1528662074038 10439909774959 1822373103148 -6974433017907 6309247250385 11141586625400 16517676644164 -17331800423448 18505534619011 -19766744660346 6180770287595 10091989087414 568941650316 -16088179604413 4394384705024 -12261134024334 5922925172362 -15877810472552 ...

output:

84539

result:

ok single line: '84539'

Test #12:

score: 0
Accepted
time: 424ms
memory: 11608kb

input:

400
15303324246439 -3723332555981 13456786049020 -5449703381253 14800811164417 14869669832774 -8935406726744 17188618255567 -969955969860 -9782415306754 313401398018 -11039462554654 14986021405358 -14416653774872 8383500342130 -10016955880319 -7595947546269 5157260185522 -1603222670917 -337442035105...

output:

77070

result:

ok single line: '77070'

Test #13:

score: 0
Accepted
time: 452ms
memory: 12056kb

input:

400
-11778519553085 -16255960948010 -6226670878843 13615009183139 14247722110483 -13760764644121 17257861091111 -382049751137 -18229549564421 -4676037861677 16604678606012 13384796753704 4798803674372 -18237959122017 -17890402024503 11526905501044 -5896272864489 15870583446522 -16438263365549 -14109...

output:

88826

result:

ok single line: '88826'

Test #14:

score: 0
Accepted
time: 436ms
memory: 11040kb

input:

400
-5060891419563 11194603021718 7518136467372 10357185701947 3989891421036 8420213756689 2761846713999 -15866137191314 14511434162949 -13547972272308 -11341077208438 1850394936472 6759473618586 -17545628892952 -136933759604 -15416862622640 -1971715904134 -13646627103589 13279907642860 -18895466094...

output:

83447

result:

ok single line: '83447'

Test #15:

score: 0
Accepted
time: 444ms
memory: 11368kb

input:

400
16919086217506 -6384989605958 -13202792652870 -7863676941990 3731048765018 -19255446045143 18393484233509 -4251490219988 15024709618745 -6265764232502 -10565233317818 3772903365601 -9818067060798 -16415763429312 -15128974796983 2275660459409 3297900503632 16182058464702 7219597158423 -7370341301...

output:

86523

result:

ok single line: '86523'

Test #16:

score: -100
Time Limit Exceeded

input:

400
762 330 158 514 666 258 152 512 342 310 622 476 760 224 92 480 134 98 128 474 578 792 528 274 364 256 424 444 596 418 198 516 404 736 756 664 366 86 794 414 524 748 660 602 200 396 652 398 368 12 332 738 106 34 508 168 136 170 458 620 644 234 482 742 138 236 548 56 772 18 36 522 504 636 150 570 ...

output:

10706600

result: