Submission #1209328

#TimeUsernameProblemLanguageResultExecution timeMemory
1209328SpyrosAlivNafta (COI15_nafta)C++20
34 / 100
1097 ms32120 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; const int MN = 2001; int grid[MN][MN], c[MN][MN], dp[MN][MN], fin[MN], n, m, lb, rb, s; bool vis[MN][MN]; bool inside(int i, int j) { return i >= 1 && i <= n && j >= 1 && j <= m; } void flood(int i, int j) { s += grid[i][j]; vis[i][j] = true; lb = min(lb, j); rb = max(rb, j); for (auto [pi, pj]: delta) { int ni = i + pi; int nj = j + pj; if (inside(ni, nj) && grid[ni][nj] != -1 && !vis[ni][nj]) { flood(ni, nj); } } } void dnc(int l, int r, int optl, int optr, int k) { if (l > r) return; int mid = (l + r) >> 1; int best = -1, opt = -1; for (int i = optl; i <= min(optr, mid); i++) { int ans = c[i][mid]; if (i > 1 && k > 1) ans += dp[i-1][k-1]; if (ans > best) { best = ans; opt = i; } } dp[mid][k] = best; fin[k] = max(fin[k], best); dnc(l, mid - 1, optl, opt, k); dnc(mid+1, r, opt, optr, k); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char c; cin >> c; if (c == '.') { grid[i][j] = -1; } else grid[i][j] = (c - '0'); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (vis[i][j] || grid[i][j] == -1) continue; s = 0; lb = j; rb = j; flood(i, j); for (int i = 1; i <= m; i++) { if (i > lb || rb < i) break; c[i][lb] += s; c[i][rb+1] -= s; } } } swap(n, m); for (int i = 1; i <= n; i++) { for (int j = i+1; j <= n; j++) { c[i][j] += c[i][j-1]; } } for (int k = 1; k <= n; k++) { dnc(1, n, 1, n, k); } for (int i = 1; i <= n; i++) cout << fin[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...