Submission #676288

#TimeUsernameProblemLanguageResultExecution timeMemory
676288Do_you_copyDomino (COCI15_domino)C++17
30 / 160
309 ms47716 KiB
//Then #include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ld = long double; using pii = pair <int, int>; mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 2e3 + 10; //const int Mod = 1e9 + 7; const int inf = 0x3f3f3f3f; int n, k; int a[maxN][maxN]; int dx[] = {0, 0, -1, 1}; int dy[] = {-1, 1, 0, 0}; struct TEdge{ int u, v, c, w; }; vector <TEdge> S; vector <int> adj[maxN]; bool inqueue[maxN]; int trace[maxN]; int d[maxN]; int conv(int x, int y){ if (x > n || y > n || !x || !y) return 0; return (x - 1) * n + y; } void add_edge(int u, int v, int c, int w){ w = -w; adj[u].pb(S.size()); S.pb({u, v, c, w}); adj[v].pb(S.size()); S.pb({v, u, 0, -w}); } void MCMF(){ fill(d, d + n * n + 2, inf); d[0] = 0; queue <int> Q; Q.push(0); while (!Q.empty()){ int u = Q.front(); inqueue[u] = 0; Q.pop(); for (int i: adj[u]){ int v = S[i].v, c = S[i].c, w = S[i].w; if (!c || d[v] <= d[u] + w) continue; d[v] = d[u] + w; trace[v] = i; if (!inqueue[v]){ inqueue[v] = 1; Q.push(v); } } } } void Init(){ cin >> n >> k; int sum = 0; for (int i = 1; i <= n; ++i){ for (int j = 1; j <= n; ++j){ cin >> a[i][j]; } } for (int i = 1; i <= n; ++i){ for (int j = 1; j <= n; ++j){ sum += a[i][j]; if ((i + j) & 1){ add_edge(conv(i, j), n * n + 1, 1, 0); continue; } add_edge(0, conv(i, j), 1, 0); for (int k = 0; k < 4; ++k){ int v = conv(i + dx[k], j + dy[k]); if (!v) continue; add_edge(conv(i, j), v, 1, a[i][j] + a[i + dx[k]][j + dy[k]]); } } } while (k--){ MCMF(); int v = n * n + 1; sum += d[v]; while (v){ int i = trace[v]; S[i].c ^= 1; S[i ^ 1].c ^= 1; v = S[i].u; } } cout << sum; } #define debug #define taskname "test" signed main(){ faster if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } int tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000); timeout.close(); #ifndef debug cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n"; #endif // debug } }

Compilation message (stderr)

domino.cpp: In function 'int main()':
domino.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
domino.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...