Submission #1018458

#TimeUsernameProblemLanguageResultExecution timeMemory
1018458caterpillowDomino (COCI15_domino)C++17
0 / 160
763 ms519576 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pl = pair<ll, ll>; using pi = pair<int, int>; #define vt vector #define f first #define s second #define pb push_back #define all(x) x.begin(), x.end() #define size(x) ((int) (x).size()) #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define F0R(i, b) FOR (i, 0, b) #define endl '\n' const ll INF = 1e18; const int inf = 1e9; template<template<typename> class Container, typename T> ostream& operator<<(ostream& os, Container<T> o) { os << "{"; int g = size(o); for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); os << "}"; return os; } void _print() { cerr << "\n"; } template<typename T, typename ...V> void _print(T t, V... v) { cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef LOCAL #define dbg(x...) cerr << #x << " = "; _print(x); #else #define dbg(x...) #define cerr if (0) std::cerr #endif /* max cost max flow? */ struct Queue { int i = 0; vt<int> q; int pop() { return q[i++]; } void push(int v) { q.pb(v); } bool empty() { return i == size(q); } }; struct Edge { int u, v; int flo, cost; }; // max cost struct MCMF { int n; vt<Edge> edges; vt<vt<int>> adj; void init(int _n) { n = _n; adj.resize(n); F0R (i, n - 2) adj[i].reserve(4); adj[n - 2].reserve(n / 2); adj[n - 1].reserve(n / 2); } void ae(int u, int v, int cost) { int ei = size(edges); edges.pb({u, v, 0, cost}); adj[u].pb(ei); adj[v].pb(~ei); } bool valid(int ei) { if (ei >= 0) return edges[ei].flo == 0; else return edges[~ei].flo == 1; } pi get_edge(int u, int ei) { if (ei >= 0) return {edges[ei].v, edges[ei].cost}; else return {edges[~ei].u, -edges[~ei].cost}; } int find_augmenting_path(int s, int t) { vt<int> par(n, -1); // parent edge vt<int> dist(n, inf); dist[s] = 0; vt<bool> in_queue(n); Queue q; q.push(s); while (!q.empty()) { int u = q.pop(); in_queue[u] = false; for (int ei : adj[u]) { if (!valid(ei)) continue; auto [v, cost] = get_edge(u, ei); if (dist[u] + cost < dist[v]) { dist[v] = dist[u] + cost; par[v] = ei; if (!in_queue[v]) { q.push(v); in_queue[v] = true; } } } } int u = t; while (par[u] != -1) { if (par[u] >= 0) edges[par[u]].flo = 1, u = edges[par[u]].u; else edges[~par[u]].flo = 0, u = edges[~par[u]].v; } return dist[t]; } int calc(int s, int t, int k) { int ans = 0; F0R (_, k) ans += find_augmenting_path(s, t); return ans; } }; int n, k; vt<vt<int>> grid; MCMF mcmf; main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> k; grid.resize(n, vt<int>(n)); ll tot = 0; F0R (r, n) { F0R (c, n) { cin >> grid[r][c]; tot += grid[r][c]; } } mcmf.init(n * n + 2); int s = n * n; int t = s + 1; const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; auto enc = [&] (int r, int c) { return r * n + c; }; F0R (r, n) { F0R (c, n) { if ((r + c) % 2 == 0) continue; F0R (i, 4) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nc >= 0 && nr < n && nc < n) { mcmf.ae(enc(r, c), enc(nr, nc), 0); } } } } F0R (r, n) { F0R (c, n) { if ((r + c) % 2 == 1) mcmf.ae(s, enc(r, c), 1000 - grid[r][c]); else mcmf.ae(enc(r, c), t, 1000 - grid[r][c]); } } return 0; int flow = mcmf.calc(s, t, k); int ans = 2 * k * 1000 - flow; cout << tot - ans << endl; }

Compilation message (stderr)

domino.cpp:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  138 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...