Submission #1209320

#TimeUsernameProblemLanguageResultExecution timeMemory
1209320SpyrosAlivNafta (COI15_nafta)C++20
0 / 100
1 ms1088 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; const int MN = 2005; int grid[MN][MN], c[MN][MN], dp[MN][MN], n, m, lb, rb, s; bool vis[MN][MN]; vector<tuple<int, int, int>> rr; 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) / 2; int best = -1, opt = -1; for (int i = optl; i <= min(optr, mid); i++) { int ans = c[i][mid]; if (i > 1) ans += dp[i-1][k-1]; if (ans > best) { best = ans; opt = i; } } dp[mid][k] = best; dnc(l, mid - 1, optl, opt, k); dnc(mid+1, r, opt, optr, k); } void solve() { 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 = m; rb = 0; flood(i, j); rr.push_back({lb, rb, s}); } } swap(n, m); for (auto [l, r, s]: rr) { for (int i = 1; i <= n; i++) { if (i > l || r < i) break; c[i][l] += s; c[i][r+1] -= s; } } for (int i = 1; i <= n; i++) { for (int j = i+1; j <= n; j++) { c[i][j] += c[i][j-1]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i][1] = max(dp[i][1], c[1][j]); } } for (int k = 2; k <= n; k++) { dnc(1, n, 1, n, k); } for (int i = 1; i <= n; i++) { cout << dp[n][i] << "\n"; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...