#include<bits/stdc++.h>
#include"homecoming.h"
using namespace std;
typedef long long ll;
const int maxn = 6e6 + 20;
const int maxm = 6e7 + 20;
const int inf = 1e9 + 7;
int cnt = 0, to[maxm], cap[maxm], last[maxn], pre[maxm], pos[maxn];
void add_edge(int v, int u, int c){
to[cnt] = u, cap[cnt] = c, pre[cnt] = last[v], last[v] = cnt ++;
to[cnt] = v, cap[cnt] = 0, pre[cnt] = last[u], last[u] = cnt ++;
}
int dis[maxn];
int dfs(int source, int sink, int untilnow){
if (source == sink)
return untilnow;
int now = 0;
for (int &ed = pos[source]; ed != -1; ed = pre[ed]){
if (cap[ed] and dis[to[ed]] == dis[source]+1){
int cur = dfs (to[ed], sink, min (cap[ed], untilnow));
cap[ed] -= cur, cap[ed^1] += cur, now += cur, untilnow -= cur;
if (untilnow == 0)
return now;
}
}
return now;
}
int Q[maxn], head = 0, tail = 0;
bool bfs(int n, int source, int sink){
for (int i = 0; i < n; i++)
dis[i] = -1;
dis[source] = 0;
tail = head = 0;
Q[head++] = source;
while (tail < head){
int cur = Q[tail++];
for (int ed = last[cur]; ed != -1; ed = pre[ed]){
if (cap[ed] and dis[to[ed]] == -1){
Q[head++] = to[ed];
dis[to[ed]] = dis[cur]+1;
}
}
}
return dis[sink] != -1;
}
ll max_flow(int n, int src, int snk){
ll maxFlow = 0;
while (bfs(n, src, snk)){
for (int i = 0; i < n; i++)
pos[i] = last[i];
maxFlow += dfs(src, snk, inf);
}
return maxFlow;
}
int lc[maxn], rc[maxn];
int newint;
void add(int id, int L, int R, int l, int r, int idx){
if (r <= L or R <= l)
return;
if (l <= L and R <= r){
add_edge(idx, id, inf);
return;
}
int mid = (L + R) >> 1;
add(lc[id], L, mid, l, r, idx);
add(rc[id], mid, R, l, r, idx);
}
int N;
int build(int L, int R){
if (L + 1 == R)
return L+N;
int me = newint ++;
int mid = (L+R)>>1;
lc[me] = build(L, mid);
rc[me] = build(mid, R);
return me;
}
ll solve(int n, int k, int* a, int* b){
N = n;
cnt = 0;
int src = 2*n, snk = 2*n+1;
for (int i = 0; i < 3*n+2; i++)
last[i] = -1;
newint = 2*n+2;
int root = build(0, n);
for (int i = 0; i < n; i++){
int j = i + k;
if (j < n)
add(root, 0, n, i, j, i);
else{
add(root, 0, n, i, n, i);
add(root, 0, n, 0, k-n+i, i);
}
}
for (int i = 0; i < n; i++)
for (int j = i; j < i+k; j++)
add_edge(i, n+j%n, inf);
for (int i = 0; i < n; i++){
add_edge(src, i, a[i]);
add_edge(n+i, snk, b[i]);
}
ll sum = 0;
for (int i = 0; i < n; i++)
sum += a[i];
return max(0ll, sum - max_flow(newint, src, snk));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
220 ms |
5308 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
220 ms |
5308 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1408 KB |
Output is correct |
| 6 |
Runtime error |
179 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1097 ms |
128180 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
220 ms |
5308 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1664 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1408 KB |
Output is correct |
| 6 |
Runtime error |
179 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Halted |
0 ms |
0 KB |
- |
