QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624330#7064. Spybright_ml#TL 979ms8908kbC++203.4kb2024-10-09 15:34:202024-10-09 15:34:21

Judging History

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

  • [2024-10-09 15:34:21]
  • 评测
  • 测评结果:TL
  • 用时:979ms
  • 内存:8908kb
  • [2024-10-09 15:34:20]
  • 提交

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];

const int V = 805;
const int E = 200005;
struct MaxFlow {
    int s, t, vtot;
    int head[V], etot, cur[V];
    int pre[V];
    bool vis[V];
    int dis[V], cost, flow;

    const int inf = 1e9;
    struct edge {
        int v, nxt;
        int f, c;
    } e[E * 2];

    void addedge(int u, int v, int f, int cc, int f2 = 0) {
//        cout << u << ' ' << v << ' ' << f << ' ' << cc << '\n';
        e[etot] = {v, head[u], f, cc}; head[u] = etot++;
        e[etot] = {u, head[v], f2, -cc}; head[v] = etot++;
    }

    bool spfa() {
        for(int i = 1; i <= vtot; i++) {
            dis[i] = inf;
            vis[i] = false;
            pre[i] = -1;
            cur[i] = head[i];
        }
        dis[s] = 0;
        vis[s] = true;
        queue<int> q;
        q.push(s);
        while(!q.empty()) {
            int u = q.front();
            for(int i = head[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if(e[i].f && dis[v] > dis[u] + e[i].c) {
                    dis[v] = dis[u] + e[i].c;
                    pre[v] = i;
                    if(!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
            q.pop();
            vis[u] = false;
        }
        return dis[t] < inf;
    }

    void augment() {
        int u = t;
        int f = inf;
        while(~pre[u]) {
            f = min(f, e[pre[u]].f);
            u = e[pre[u] ^ 1].v;
        }
        flow += f;
        cost += f * dis[t];
        u = t;
        while(~pre[u]) {
            e[pre[u]].f -= f;
            e[pre[u] ^ 1].f += f;
            u = e[pre[u] ^ 1].v;
        }
    }

    PII sol() {
        cost = flow = 0;
        while(spfa()) {
            augment();
        }
        return {flow, cost};
    }

    void init(int s_, int t_, int vtot_) {
        s = s_;
        t = t_;
        vtot = vtot_;
        etot = 0;
        for(int i = 1; i <= vtot; i++) head[i] = -1;
    }
} g;

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;
    g.init(s, t, t);
    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;
                }
            }
//            cout << i << ' ' << j << ' ' << sum << '\n';
            g.addedge(i, n + j, 1, -sum[l]);
        }
    }
    cout << -g.sol().se << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 979ms
memory: 8908kb

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: 3892kb

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: -100
Time Limit Exceeded

input:

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

output:

160000

result: