#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 2000;
const int K = 110;
const int PW = 20;
struct edge{
int x, y, cap, flow;
edge(int _x, int _y, int _c, int _f): x(_x), y(_y), cap(_c), flow(_f) {}
};
vector<edge> edges;
queue<int> q;
vector<int> g[N];
int ans = 0, s, t, n, m, k, dst[N], ptr[N];
void add_edge(int x, int y, int cap){
g[x].PB(sz(edges));
edges.PB(edge(x, y, cap, 0));
g[y].PB(sz(edges));
edges.PB(edge(y, x, 0, 0));
}
bool bad(int l, int r, int v){
if (v == s || v == t || v < m) return 0;
return !(m + l <= v && v <= m + r);
}
bool bfs(int l, int r){
fill(dst, dst + t + 1, oo);
dst[s] = 0;
while (sz(q)) q.pop();
q.push(s);
while (sz(q)){
int v = q.front(); q.pop();
for (int nm : g[v]){
edge u = edges[nm];
if (!bad(l, r, u.y) && u.cap > u.flow && dst[u.y] > dst[v] + 1){
dst[u.y] = dst[v] + 1;
q.push(u.y);
}
}
}
return (dst[t] < oo);
}
int dfs(int v, int pshd){
if (pshd == 0) return 0;
if (v == t) return pshd;
for (; ptr[v] < sz(g[v]); ptr[v]++){
int nm = g[v][ptr[v]];
edge u = edges[nm];
if (dst[u.y] != dst[v] + 1) continue;
int nw = dfs(u.y, min(pshd, u.cap - u.flow));
if (nw){
edges[nm].flow += nw;
edges[nm ^ 1].flow -= nw;
return nw;
}
}
return 0;
}
bool ok(int l, int r){
if (r - l + 1 < m) return 0;
int flow = 0;
for (int i = 0; i < m; i++) {
int nm = g[s][i];
flow += bool(edges[nm].cap == edges[nm].flow);
}
while (bfs(l, r)){
fill(ptr, ptr + t + 1, 0);
int pshd = dfs(s, oo);
while (pshd > 0){
flow += pshd;
pshd = dfs(s, oo);
}
}
return (flow == m);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < k; i++){
int x, y; cin >> y >> x;
x--; y--;
add_edge(x, m + y, 1);
}
s = n + m;
t = n + m + 1;
for (int i = 0; i < m; i++)
add_edge(s, i, 1);
for (int i = 0; i < n; i++)
add_edge(i + m, t, 1);
for (int l = 0, r = 0; l < n; l++){
if (l + m - 1 >= n) break;
while (r < n && !ok(l, r))
r++;
if (r >= n) break;
ans += n - r;
int nm = g[t][l];
if (edges[nm].cap == edges[nm].flow) continue;
int pr = -1, cr = m + l;
for (int it = 0; it < sz(g[cr]); it++){
int nm = g[cr][it];
edge ed = edges[nm];
if (ed.y != t && ed.cap > ed.flow){
pr = ed.y;
break;
}
}
nm = g[s][pr];
edges[nm].flow--;
edges[nm ^ 1].flow++;
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
380 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
428 KB |
Output is correct |
14 |
Correct |
2 ms |
248 KB |
Output is correct |
15 |
Correct |
2 ms |
380 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
380 KB |
Output is correct |
19 |
Correct |
6 ms |
632 KB |
Output is correct |
20 |
Correct |
3 ms |
504 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
100 ms |
1212 KB |
Output is correct |
26 |
Correct |
23 ms |
632 KB |
Output is correct |
27 |
Correct |
3 ms |
504 KB |
Output is correct |
28 |
Correct |
4 ms |
504 KB |
Output is correct |
29 |
Correct |
29 ms |
1196 KB |
Output is correct |
30 |
Correct |
23 ms |
1204 KB |
Output is correct |
31 |
Correct |
675 ms |
3260 KB |
Output is correct |
32 |
Correct |
34 ms |
888 KB |
Output is correct |
33 |
Correct |
13 ms |
504 KB |
Output is correct |
34 |
Correct |
22 ms |
632 KB |
Output is correct |
35 |
Correct |
320 ms |
5784 KB |
Output is correct |
36 |
Correct |
217 ms |
6012 KB |
Output is correct |
37 |
Runtime error |
3 ms |
696 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
38 |
Runtime error |
22 ms |
6556 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
39 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
40 |
Runtime error |
3 ms |
604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
41 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
42 |
Runtime error |
4 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
43 |
Runtime error |
4 ms |
1144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
44 |
Runtime error |
6 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
45 |
Runtime error |
3 ms |
552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
46 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
47 |
Runtime error |
3 ms |
652 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
48 |
Runtime error |
4 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
49 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
50 |
Runtime error |
3 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |