Submission #1209330

#TimeUsernameProblemLanguageResultExecution timeMemory
1209330SpyrosAlivNafta (COI15_nafta)C++20
100 / 100
332 ms110152 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], tot[MN], n, m, lb, rb, s; bool vis[MN][MN]; vector<vector<pair<int, int>>> rr(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); tot[lb] += s; rr[rb].push_back({lb, s}); } } swap(n, m); for (int i = 1; i <= n; i++) { for (int j = i; j >= 1; j--) { if (i == j) c[j][i] = tot[i]; else c[j][i] = c[j+1][i] + tot[j]; } for (auto [ll, ss]: rr[i]) { tot[ll] -= ss; } } for (int k = 1; k <= n; k++) { dnc(1, n, 1, n, k); cout << fin[k] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...