Submission #552893

#TimeUsernameProblemLanguageResultExecution timeMemory
552893JomnoiNafta (COI15_nafta)C++17
100 / 100
333 ms39748 KiB
#include <bits/stdc++.h> #define DEBUG false using namespace std; const int MAX_N = 2e3 + 10; const int INF = 1e9 + 7; const int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; char table[MAX_N][MAX_N]; int value[MAX_N], intersect[MAX_N][MAX_N]; int dp[MAX_N][MAX_N]; bool visited[MAX_N][MAX_N]; void solve(const int &k, const int &l, const int &r, const int &a, const int &b) { if(l > r) { return; } int mid = (l + r) / 2, pos; dp[k][mid] = -INF; for(int i = a; i <= min(mid, b); i++) { int res = dp[k - 1][i - 1] + value[mid] - intersect[i - 1][mid]; if(dp[k][mid] < res) { dp[k][mid] = res; pos = i; } } solve(k, l, mid - 1, a, pos); solve(k, mid + 1, r, pos, b); } int main() { cin.tie(nullptr)->sync_with_stdio(false); int R, S; cin >> R >> S; for(int i = 1; i <= R; i++) { cin >> (table[i] + 1); } queue <pair <int, int>> q; for(int i = 1; i <= R; i++) { for(int j = 1; j <= S; j++) { if(visited[i][j] == true or table[i][j] == '.') { continue; } visited[i][j] = true; q.emplace(i, j); int min_S = S, max_S = 0, sz = 0; while(!q.empty()) { auto [ux, uy] = q.front(); q.pop(); sz += table[ux][uy] - '0'; min_S = min(min_S, uy); max_S = max(max_S, uy); for(int i = 0; i < 4; i++) { int vx = ux + d[i][0], vy = uy + d[i][1]; if(vx < 1 or vx > R or vy < 1 or vy > S or visited[vx][vy] == true or table[vx][vy] == '.') { continue; } visited[vx][vy] = true; q.emplace(vx, vy); } } for(int s = min_S; s <= max_S; s++) { value[s] += sz; for(int s2 = s + 1; s2 <= max_S; s2++) { intersect[s][s2] += sz; } } } } for(int i = 1; i <= S; i++) { dp[1][i] = value[i]; } cout << *max_element(dp[1] + 1, dp[1] + S + 1) << '\n'; for(int i = 2; i <= S; i++) { solve(i, i, S, i, S); cout << *max_element(dp[i] + 1, dp[i] + S + 1) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...