QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624330 | #7064. Spy | bright_ml# | TL | 979ms | 8908kb | C++20 | 3.4kb | 2024-10-09 15:34:20 | 2024-10-09 15:34:21 |
Judging History
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